Tradicionalmente se le consideró original de Cauca (Coca, Segovia), como parecen afirmar Hidacio y Zósimo, pero este hecho ha sido puesto en duda, abogándose por Itálica como ciudad natal. En cualquier caso, de origen hispano, era hijo del general Flavio Teodosio, conocido como Teodosio el Viejo, militar de renombre que obtuvo los títulos de conde (con un significado diferente al que se le da hoy día) y magister equitum praesentalis en la corte de Valentiniano I (364-375). Debido a sus éxitos fue enviado a Britania en el año 368, acompañado por su hijo, que se familiarizó con la realidad más cruda del Imperio, y más tarde a África (373-374) donde padre e hijo volvieron a destacar.