Однако эти брачные планы были расторгнуты Стефаном III Молдавским. Молдавский господарь к этому времени был женат на Маргупской принцессе Марии. Мария Мангупская будучи родственницей князю Исааку и происходила из соперничавшей семьи. Её брат Александр, потерпев поражение в борьбе за престол Мангупа, жил в Молдавии при дворе зятя. Стефан III нуждавшийся в союзниках и экономически зависящий от крымской торговли был заинтересован в политических отношениях с этим православным княжеством. И, видимо, с князем Исааком у него не всё ладилось. Поэтому Молдавский правитель помог шурину. Господарь дал Александру 300 воинов и нанял итальянское судно, которое перевезло претендента на Мангупский престол в Крым. В конце 1474 начале 1475 года Александр сверг князя Исаака и занял престол Феодоро. С отстранением от власти князя Исаака прекратились и брачные переговоры.
Но в 1475 году княжество Феодоро было захвачено турками. Таким образом, Москва лишилась союзника в Крыму. Возможно, это обстоятельство так же способствовало налаживанию молдавско-московских отношений.
Приняв положительное решение о браке наследника, из Москвы в апреле 1480 года в Крым к хану был отправлен великокняжеский посол князь Иван Иванович Звенец Звенигородский (умер 1504). В составе московского посольства находился доверенный человек княгини Феодосии Олельковны. Он должен был уведомить Молдавского господаря о начале подготовки к свадьбе. При этом, на основании указаний, сделанных Звенигородскому князю можно утверждать, что Москва очень была заинтересована в этом династическом браке. Князь Иван Звенц получил наказ, что в случае если доверенный человек княгини Феодосии Олельковны в дороге вдруг заболеет, то не следовало дожидаться его выздоровления, а отправить в Молдавию дьяка Сухова. Послу предписывалось в Москву без письма Молдавского господаря не возвращаться.
Русское правительство, как в воду глядело. Доверенный человек княгини Феодосии действительно в дороге «занемог» и обязанности свадебного посла были возложены на московского дьяка Сухова.
Князь Иван Звенигородский отправился в Крым, а дьяк Сухов прибыл в резиденцию Молдавского господаря в город Сучавы. Сухов стал первым русским представителем в Молдавии.
Получив заверения на брак дочери от господаря Стефана III, дьяк должен был присоединиться в Крыму к посольству князя Ивана Звенца Звенигородского, после чего они должны были вернуться в Москву.
Посольство длилось целый год. Известно, что Иван Звенец вернулся в Москву до 26 апреля 1481 года, так как к этому числу молдавские послы, несомненно, прибывшие на Русь совместно с московским посольством, уже находились по пути домой. Положительное решение было достигнуто к началу 1482 году. Поскольку уже 28 марта 1482 года Польский король Казимир, несомненно, уведомлённый о предстоящей свадьбе, через владения которого должен был следовать свадебный кортеж, подписал сохранный лист для княгини Елены Стефановны. В сохранном листе был указан маршрут свадебной процессии. Снятын – Теребовль – Львов – Белз – Хельм – Брест.
На стыке весны и лета 1482 года в Молдавию за невестой были отправлены московские послы – братья боярин Андрей (умер 1491) и боярин Пётр (умер около 1511) Михайловичи Плещеевы.
Плещеевы происходили из старинного московского боярского рода, предок которых Фёдор Бяконт служил ещё Московскому князю Симеону Гордому, правившему в 1340 – 1353 годах. А его сын Святой Алексей (1292/3 – 12.2.1378), митрополит Московский и всея Руси в 1354 – 1378 годах, был наставником великого князя Дмитрий Донского.
Весь ход переговоров не отражён в летописях, но о традиции династических браков мы можем судить по браку дочери Иван и Софьи Палеолог – Елены Ивановны с великим Литовским князем Александром.
Московские послы, несомненно, преподнесли богатые подарки Молдавскому господарю и его супруги. Один из братьев Плещеевых, очевидно, старший Андрей Михайлович, выслуживший боярство ещё в 1478 году, должен быть исполнять роль жениха во время помолвки в Сучаве, что было делом распространённым. Так поступали московские послы в Риме во время помолвки принцессы Софьи Палеолог с Московским князем Иваном III.
Выполнив все положенные в деле бракосочетания церемонии, свадебная процессия отправилась в Москву.