Jabarkan Kehidupan sebagai permaisuri dari Aelia Eudocia

Legenda mengisahkan bahwa ketika Theodosius II berumur 20 tahun, dia ingin menikah. Dia berbicara dengan adiknya Pulcheria, yang mulai mencari seorang gadis yang cocok untuk kakaknya, yang baik "berdarah ningrat atau imperial." Teman semasa kecilnya Paulinus juga membantu Theodosius untuk mendapatkan jodohnya. Pencarian Kaisar kebetulan dimulai pada saat Athenais telah tiba di Konstantinopel. Pulcheria mendengar kabar tentang gadis muda tersebut, yang hanya memiliki 100 uang logam atas namanya, dan ketika ia menemuinya ia "terpesona atas kecantikannya dan atas kecerdasan yang ditunjukkan atas keluhannya." Setelah melaporkan kembali ke kakaknya, ia mengatakan bahwa ia telah "menemukan seorang gadis muda, seorang Yunani yang sangat cantik dan polos, putri dari seorang filsuf," dan Theodosius yang muda dan penuh hasrat langsung jatuh cinta kepadanya.

Athenais dibesarkan secara pagan, dan harus masuk Kristen untuk dapat menikah dengan Theodosius II. Kaisar mengganti namanya menjadi Eudocia dan memperistrinya. Mereka melangsungkan pernikahan pada tanggal 7 Juni 421 dan ada laporan yang menyatakan bahwa Theodosius merayakan pernikahan dengan ras kereta di hippodrome." Saudara-saudaranya yang menolaknya setelah kematian ayahanda mereka yang cemas akan dijatuhi hukuman setelah ia menjadi Permaisuri, melarikan diri. Namun Eudocia tidak menghukum mereka dan bahkan memanggil mereka kembali ke Konstantinopel, dan Theodosius memberikan mereka penghargaan. Ia membuat Gessius praetorian prefect di Illycricum dan membuat Valerius magister officiorum. Mereka diberikan penghargaan karena Eudocia percaya bahwa tindakan kejam mereka berasal dari kecemburuan akan takdirnya dan bukan dari tindakan balas dendam. Ia juga menjadikan sahabat baiknya, Paulinus magister officiorum, karena telah menolongnya untuk mendapatkan jodohnya. Naumun ini adalah sebuah rekayasa meskipun klaim atas keasliannya dapat diterima dikalangan sejarawan. Versi paling awal dari cerita ini muncul lebih dari satu abad setelah kematian Eudocia di dalam "Kronik dunia John Malalas, seorang penulis yang tidak selalu membedakan antara sejarah otentik dan memori popuer peristiwa yang diresapi dengan motif dongeng." Fakta bahwa ia adalah putri dari Leonitius dan awalnya memiliki nama Athenais, menurut sejarawan Yunani Socrates Konstantinopel, dan seorang sejarawan kontemporer yang bernama Priscus dari Panion; namun mereka meninggalkan peran Pulcheria di dalam permainan jodoh untuk saudaranya. Sajarawan Sozomen dan Theodoret tidak memasukkan Eudocia di dalam kisah sejarah mereka karena mereka menulisnya setelah Eudocia telah jatuh namanya.