Evdochia was born into the large House of Gediminid, as the second daughter and fourth child of Alexander Olelkovich, Prince of Kiev (d. 1454) and his wife, Anastasia of Moscow (1470), daughter of Vasily I of Moscow and Sophia of Lithuania.

She was the sister of Simeon of Kiev, and a cousin of Ivan III, Grand Prince of Moscow.

[2] Evdochia was most probably the mother of Stephen's two sons, Bogdan and Peter, according to historian Jonathan Eagles.

[3] When Stephen made a donation to the Hilandar Monastery on Mount Athos on 27 July 1466, he specified that the monks should pray for his relatives, including Evdochia and their two children, Alexandru and Olena.

[4] Alexandru was most probably identical with Stephen's first-born son and co-ruler who died in 1496, according to Eagles.