Aelia Eudoxia (d. 6 October 404) was the wife of the Eastern Roman emperor Arcadius.

The daughter of a certain Bauto , a Frankish magister militum serving in the Western Roman army during the 380s, Eudoxia owed her marriage to the youthful Emperor Arcadius on 27 April 395 to the intrigues of the eunuch of the palace, Eutropius. She had very considerable influence over her husband, who was of rather weak character and who was more interested in Christian piety than imperial politics.

In 399 she succeeded, with help from the leader of the Empire's Gothic mercenaries, in deposing her erstwhile benefactor Eutropius, who was later executed over the protests of John Chrysostom, the Patriarch of Constantinople.

John Chrysostom was already becoming unpopular at court due to his efforts at reforming the Church, and in 403 Eudoxia and Theophilus, Patriarch of Alexandria, succeeded in having the outspoken Patriarch condemned by a synod and then deposed. He was exiled to Armenia the next year after a brief return to power resulting from popular disgust at his fall and an earthquake which reinforced those feelings.

Eudoxia had a total of seven pregnancies, five of which were successful. Her final pregnancy ended in a miscarriage which led to her death on October 6, 404. One of her children was the future emperor Theodosius II.

In 403, Simplicius, Prefect of Constantinople, erected a statue dedicated to her on a column of porphyry.