Предложение Молдавского господаря заинтересовало Московского великого князя. Уже в следующем году в Молдавию убыло московское посольство. Послы вернулись в Москву в 1483 году, с ними прибыла принцесса Елена Стефановна.

С этого года начинаются постоянные обмены посольствами между Молдавией и Москвой. В Москву приезжали молдавские послы Стецко, в 1491 году, Мушат в 1492 году. Из Москвы в Сучаву, столицу Молдавии, отправлялись посольства Прокофия Зиновьева в 1486 году, Иван Лихарёва в 1490 году, Скарлата Зиновьева в 1492 году, Ивана Плещеева в 1492 году. В 1496 году русский посол Замытцкий уведомил Молдавского господаря о заключении московско-литовского мира.

Некоторое охлаждение в молдавско-московских отношениях наступило лишь после того как в 1502 году Елена Стефановна и её сын Дмитрий Внук были отстранены от власти и подверглись аресту. Но даже это не разрушило политические контакты между двумя государствами.

Стефан III умер 2 июля 1504 году. Его наследники оказались не такими успешными правителями. Внутренняя борьба за власть ослабила Молдавию. Она уже не могла противостоять внешней угрозы.

В 1538 году в Молдавию вторглась турецкая армия во главе с самим султаном Сулейманом, с востока нахлынули крымские татары, а с севера поляки. Сначала господарь Пётр Рареш (1487 – 1546) разбил османов в битве при Хотине. Но турецкая армия захватила Сучаву, и столичные бояре поспешили присягнуть на верность султану. Турки в 1538 году посадили на молдавский престол марионетку Стефана Лакусту. Именно с этого времени Молдавия окончательно попала под власть турок. Султан подчинил себе области между Прутом и Днестром, а Буджак, передал крымским татарам. Вскоре потомки Стефана III Великого и вовсе были лишены власти. Последним Мушатином на Молдавском престоле был Илияс-Александр (около 1635 – 1675), правивший в 1666 – 1668 годах.

Молдавские источники и русские летописи не содержат сведений об этапах сватовства Ивана Молодого к Молдавской принцессе. Однако крымские посольские дела, введённые в научный оборот историком К.В. Базилевичем (1892 – 1950), содержат сведения о брачных намерениях Молдавского господаря.

Во второй половине 70-х годов XV века, то есть в самый сложный период молдавско-турецкого противостояния, когда господарь Стефан III наиболее остро нуждался в союзниках, он решил устроить династический брак своей дочери Елены с наследником Московского престола. Поскольку личных контактов у Молдавского господаря с Москвой не было, то своими посредниками Стефан III выбрал родственников покойной матери Елены – князей Олельковичей.

Известно, что у Евдокии Александровны было два брата и две сестры.

Старший из братьев – Симеон Александрович (умер 3.12.1471), удельный Киевский князь в 1454 – 1471 годах, фактически независимый правитель, именовавшийся «царём Киевским». Князь Симеон был ревнителем православной веры и поддерживал тесные отношения с Северо-Восточными русскими княжествами. Но в 1471 году он умер и был похоронен в Киево-Печерской лавре.

Его младший брат Михаил Александрович (умер 30.08.1481), Слуцкий и Копыльский удельный князь в 1454 – 1481 годах, тесно связанный с Новгородом Великим. Князь Михаил Олелько был соперником великого Литовского князя Казимира Ягеллона (1427 – 1492), правившего в Литве с 1440 года и в Польше с 1447 года. Он в 1470 – 1471 годах княжил в Новгороде Великом, приглашённый антилитовской боярской группировкой. И был изгнан из города кланом Борецких, ярых противников Москвы.

Их сёстры – Ульяна (Юлиана) Александровна, супруга с 1464 года князя Юрия Фёдоровича Пронского (умер 1528), правителя удельного Пронского княжества в Рязанской земле в 1479 – 1483 годах. И Феодосия Александровна, супруга некоего князя Симеона Юрьевича.