Según Zósimo, Eudoxia comenzó su vida en Constantinopla como miembro de la casa de Promoto, "magister militum" del Imperio romano de Oriente.