В сие время явилась новая знаменитая Держава в соседстве с Литвою и сделалась предметом Иоанновой политики. Мы говорили о начале Молдавского Княжества, управляемого Воеводами, коих имена едва нам известны до самого Стефана IV, или Великого, дерзнувшего обнажить меч на ужасного Магомета II и славными победами, одержанными им над многочисленными Турецкими воинствами, вписавшего имя свое в историю редких Героев: мужественный в опасностях, твердый в бедствиях, скромный в счастии, приписывая его только Богу, покровителю добродетели, он был удивлением Государей и народов, с малыми средствами творя великое. Вера Греческая, сходство в обычаях, употребление одного языка в церковном служении и в делах государственных, необыкновенный ум обоих Властителей, Российского и Молдавского, согласие их выгод и правил служили естественною связию между ими. Стефан, кроме Турков, опасался честолюбивого Казимира и Менгли-Гирея: первый хотел, чтобы Молдавия зависела от Королевства Польского; второй, будучи присяжником Султана, угрожал ей нападением. Иоанн мог содействовать ее независимости и безопасности, обуздывая Короля страхом войны, а Менгли-Гирея дружественными представлениями, с условием, чтобы и Стефан, в случае нужды, помогал России усердно. Сей Воевода и Господарь – так называет он себя в своих грамотах, – противоборствуя насилиям Султанов, утеснителей Греции, имел еще особенное право на дружество зятя Палеологов, который принял герб их и с ним обязательство быть врагом Магометовых наследников.
Таким образом расположенные к искреннему союзу, Иоанн и Стефан утвердили оный семейственным: второй предложил выдать дочь свою, Елену, за старшего сына Иоаннова, избрав в посредницы мать Великого Князя. Боярин Михаиле Плещеев с знатною дружиною в 1482 году отправился за невестою в Молдавию, где и совершилось обручение. Стефан отпустил дочь в Россию с своими Боярами: Ланком, Синком, Герасимом и с женами их. Она ехала через Литву: Казимир не только дал ей свободный путь, но и прислал дары в знак учтивости. Прибыв в Москву после Филиппова заговенья, Елена жила в Вознесенском монастыре у матери великого Князя и до свадьбы имела время познакомиться с женихом. Их обвенчали в самый праздник Крещения. Увидим, что Судьба не благословила сего союза.