Eudoxia was a daughter of Theodosius II, Eastern Roman Emperor and his consort Aelia Eudocia. Her only known siblings, Arcadius and Flacilla, predeceased their parents.  Their paternal grandparents were Arcadius and Aelia Eudoxia. Their maternal grandfather was Leontius, a sophist from Athens. 
The identity of her maternal grandfather was first given by Socrates of Constantinople. John Malalas later gave a more detailed account of her mother's history. As summarised in The History of the Decline and Fall of the Roman Empire by Edward Gibbon, "The celebrated Athenais was educated by her father Leontius in the religion and sciences of the Greeks; and so advantageous was the opinion which the Athenian philosopher entertained of his contemporaries, that he divided his patrimony between his two sons, bequeathing to his daughter a small legacy of one hundred pieces of gold, in the lively confidence that her beauty and merit would be a sufficient portion. The jealousy and avarice of her brothers soon compelled Athenais to seek a refuge at Constantinople; and, with some hopes, either of justice or favor, to throw herself at the feet of Pulcheria. That sagacious princess listened to her eloquent complaint; and secretly destined the daughter of the philosopher Leontius for the future wife of the emperor of the East, who had now attained the twentieth year of his age. She easily excited the curiosity of her brother, by an interesting picture of the charms of Athenais; large eyes, a well— proportioned nose, a fair complexion, golden locks, a slender person, a graceful demeanor, an understanding improved by study, and a virtue tried by distress. Theodosius, concealed behind a curtain in the apartment of his sister, was permitted to behold the Athenian virgin: the modest youth immediately declared his pure and honorable love; and the royal nuptials were celebrated amidst the acclamations of the capital and the provinces. Athenais, who was easily persuaded to renounce the errors of Paganism, received at her baptism the Christian name of Eudocia; but the cautious Pulcheria withheld the title of Augusta, till the wife of Theodosius had approved her fruitfulness by the birth of a daughter, who espoused, fifteen years afterwards, the emperor of the West. The brothers of Eudocia obeyed, with some anxiety, her Imperial summons; but as she could easily forgive their unfortunate unkindness, she indulged the tenderness, or perhaps the vanity, of a sister, by promoting them to the rank of consuls and praefects."
Later historians have tended to reject the above account as too reminiscent of a fairy tale or a romance novel to be historical accurate. The exact circumstances of the introduction of Eudocia to Theodosius II and Pulcheria are considered unknown. The historical study Theodosian Empresses. Women and Imperial Dominion in Late Antiquity (1982) by Kenneth Holum, further introduced the suggestion that Leontius was a native of Antioch rather than Athens, drawing from the "traditional link" between the two cities and their philosophers. The argument is considered doubtful as the building activity of Eudocia in the 420s focused on Athens rather than Antioch.  The identity of Eudoxia's maternal grandmother is not recorded.
In 424, Eudoxia was betrothed to Valentinian III, her first cousin, once removed. The year of their betrothal was recorded by Marcellinus Comes. At the time of their betrothal, Valentinian was approximately four-years-old, Eudoxia only two.   Gibbon attributes the betrothal to "the agreement of the three females who governed the Roman world", meaning Galla Placidia, her niece Pulcheria, and Pulcheria's sister-in-law Eudocia.  Galla Placidia was Valentinian III's mother and a younger, paternal half-sister of Arcadius.  Valentinian III was at the time being prepared to claim the throne of the Western Roman Empire, which was held by Joannes. The latter was not a member of the Theodosian dynasty and thus regarded a usurper by the Eastern court. Within 424, Valentinian was proclaimed a Caesar in the Eastern court. The following year, Joannes was defeated and executed. Valentinian replaced him as Augustus of the West. 
Eudoxia and Valentinian III married on 29 October 437, in Constantinople, their marriage marking the reunion of the two halves of the House of Theodosius. The marriage was recorded by Socrates of Constantinople, the Chronicon Paschale and Marcellinus Comes.  In 439, Eudoxia was granted the title of Augusta, with the birth of their first daughter Eudocia. They also had a second daughter, Placidia.   The births and eventual fates of the two daughters were recorded by Priscus, Procopius, John Malalas and the Chronicon Paschale. 
On 16 March, 455, Valentinian III was killed in the Campus Martius, Rome by Optila and Thraustila.  According to the fragmentary chronicle of John of Antioch, a 7th century monk tentatively identified with John of the Sedre, Syrian Orthodox Patriarch of Antioch from 641 to 648 "Maximus, failing in both his hopes, was bitterly angry. He summoned Optila and Thraustila, brave Scythians who had campaigned with Aëtius and had been assigned to attend on Valentinian, and talked to them. He gave and received guarantees, put the blame for Aëtius' murder on the emperor, and urged that the better course would be to take revenge on them. Those who avenged the fallen man, he said, would justly have the greatest blessings. Not many days later, Valentinian rode in the Field of Ares with a few bodyguards and the followers of Optila and Thraustila. When he had dismounted from his horse and proceeded to archery, Optila and his friends attacked him. Optila struck Valentinian on his temple and when turned around to see the striker he dealt him a second blow on the face and felled him, and Thraustila slew Heraclius. Taking the emperor's diadem and horse, they hastened to Maximus... "(John of Antioch fr.201.4-5: Gordon trans., pp.52-53). Heraclius is identified as "a eunuch who had the greatest influence with the emperor" and his associate in murdering Aetius. 
Valentinian had no male descedants and had never designated a heir. Several candidates claimed the throne. Petronius Maximus who was the highest-ranking of all Roman senators was among them. A second candidate was Maximianus, son of Domninus. Domninus was a merchant from Egypt who had earned a considerable fortune. Maximianus had served as a domesticus, member of an elite guard unit of the late Roman Empire, under Aetius. Eudoxia promoted her own candidate, in the person of Majorian. 
John of Antioch reports of Maximus securing his own succession by buying the loyalties of palace officials and the local military. Eudoxia was forced to marry him or face execution. Their marriage securing the connection of Maximus to the Theodosian dynasty. Prosper of Aquitaine reports that Maximus befriended the murderers of Valentinian III instead of punishing them. Both Prosper and Victor of Tonnena place the marriage of Eudoxia to Maximus only days following the death of her first husband, commenting with dissaprooval that the empress was not given a period to grieve for Valentinian. 
John of Antioch mentions, but does not name, a previous wife of Maximus. She had reportedly been raped by Valentinian III, an event which the chronicle sees as the reason turning Maximus against his former master. The eventual fate of his first wife is not recorded.  She may be presumed to have committed suicide, following the example of Lucretia. Regardless, Maximus arranged the marriage of his son Palladius to his new stepdaughter Eudocia, the daughter of Eudoxia from her first marriage. Again to secure a dynastic relation to the Theodosian dynasty. 
The historical study "Fifth-century Gaul: A Crisis of Identity?" (1992) by John Drinkwaterand Hugh Elton considers it likely that the first wife of Maximus was also a sister to Avitus, his magister militum (Master of Soldiers). The writers have also suggested Flavius Magnus was another son of Maximus from his first marriage. Considering Flavius Probus to be a grandson. They also argue for placing the marriage of Placidia the Younger to Olybrius at this point, considering it to be the third marriage between a member of the Theodosian dynasty and a member of the extended Anicii family within the same year. They view Olybrius as a third son of Maximus, grandson through him of Flavius Anicius Probinus and grand-nephew of Flavius Anicius Hermogenianus Olybrius.  However, considering the other possible filiation of Flavius Magnus given by Christian Settipani,  as well as the lack of the name of Flavius Probus' mother, it can be assumed that he was a grandson of Petronius Maximus but from his mother.
Maximus appointed Avitus as his Magister militum praesentalis ("Master of Soldiers in Attendance") and send him to Toulouse. There Avitus was to try to secure the loyalty of Theodoric II of the Visigoths to the new emperor. However his reign was to prove short. 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 came suddenly to Rome with his forces and captured the city, and having destroyed Maximus and all his forces, he took everything from the palace, even the bronze statues. 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. After he had returned, Gaiseric gave the younger Eudocia, a maiden, the daughter of the empress Eudoxia, to his son Huneric in marriage, and he held them both, the mother and the daughter, in great honor "(Chron. 366).
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. According to Prosper, Maximus was in Rome when the Vandals arrived. He gave anyone who could permission to flee the city. He attempted to flee himself but was assassinated by the imperial slaves. He had reigned for seventy-seven days. His body was thrown into the Tiber and never recovered. Victor of Tonnena agrees, adding the detail that Pope Leo I negotiated with Geiseric for the security of the city's population. 
Hydatius attributes the assassination to revolting troops of the Roman army, enraged at Maximus' attempted flight. The Chronica Gallica of 511 attributes the assassination to a rioting crowd. Jordanes identifies a single assassin as "Ursus, a Roman soldier". Ursus is Latin for "bear". Sidonius Apollinaris makes a cryptic comment regarding a Burgundian whose "traitorous leadership" led the crowd to panic and to the slaughter of the Emperor. His identity is unknown, persumably a general who failed to face the Vandals for one reason or the other. Later historians have suggested two high-ranking Burgundians as possible candidates, Gondioc and his brother Chilperic. Both joined Theodoric II in invading Hispania later in 455. 
The three women stayed prisoners in Carthage for seven years. In 462, Leo I, Eastern Roman Emperor paid a large ransom for Eudoxia and her daughter Placidia. Eudoxia returned to Constantinople after an absence of twenty-five years, Placidia joining her. Eudocia stayed in Africa as wife of Huneric. They were parents to Hilderic, king of the Vandals from 523 to 530.