Eudoxia was born in 422, the daughter of Theodosius II, Eastern Roman Emperor and his consort Aelia Eudocia, a woman of Athenian origin.

Valentinian III was at the time being prepared to claim the throne of the Western Roman Empire, which was held by Joannes.

[4] Eudoxia and Valentinian III married on 29 October 437, in Thessalonike, their marriage marking the reunion of the two halves of the House of Theodosius.

[6] The births and eventual fates of the two daughters were recorded by Priscus, Procopius, John Malalas and the Chronicon Paschale.

[9] John of Antioch reports that Petronius Maximus, the highest-ranking of all Roman senators, secured the position of emperor by buying the loyalties of palace officials and the local military.

Both Prosper and Victor of Tonnena place the marriage of Eudoxia to Maximus only days following the death of her first husband, commenting with disapproval that the empress was not given a period to grieve for Valentinian.

According to the chronicler Malchus, "Around this time, the empress Eudoxia, the widow of the emperor Valentinian and the daughter of the emperor Theodosius and Eudocia, remained unhappily at Rome and, enraged at the tyrant Maximus because of the murder of her spouse, she summoned the Vandal Gaiseric, king of Africa, against Maximus, who was ruling Rome.

He even led away as captives surviving senators, accompanied by their wives; along with them he also carried off to Carthage in Africa the empress Eudoxia, who had summoned him; her daughter Placidia, the wife of the patrician Olybrius, who then was staying at Constantinople; and even the maiden Eudocia.

[9] Eudoxia was presumably following the example of her sister-in-law Justa Grata Honoria, who had summoned Attila the Hun for help against an unwanted marriage.