Брачные переговоры начались в 1492 году и продолжались более двух лет без вреда для военных действий. Паны литовские первые высказали эту мысль московским боярам. Раз начало было успешно, официальные послы принялись за его продолжение в конце того же года. Их образ действий служит отражением нравов того времени; получив поручения уведомить о смерти Казимира и восшествия на престол нового государя, они приступили в деликатному брачному вопросу только тогда, когда вино развязало язык. Русские, не видевшие еще дна в своих стаканах, осмотрительно ответили, что лучше заниматься миром. Поистине с обеих сторон желали окончания войны и даже брачного союза: Александр чувствовал свою слабость в военном отношении, Иван же битвам предпочитал интриги и переговоры. Если великий князь выказывал мало поспешности, это служило признаком только того, что он занимал положение для предстоящей дипломатической борьбы.
В надежде достигнуть соглашения, несмотря на разногласие в подробностях, в Москву в январе 1494 года прибыло посольство. Проект брака был оставлен к концу. Русские прежде всего требовали занятий политическими вопросами. Как ни были оживлены прения, они продолжались недолго, и литовцы уступили во всем, согласившись на важные земельные уступки. Вязьма переходила к Ивану, который один получил выгоду от исправления границ. Их честолюбие точно так же было принесено в жертву, и титул «государя всея России» был признан за великим князем Московским под условием, чтобы он отказался от притязаний на Киев – священную колыбель русской народности. Столь уступчивые противники заслуживали того, чтобы стать друзьями, и ничего не препятствовало больше их государю стать зятем Ивана, который предлагал ему взамен дешевые обещания мира с Крымом и Молдавией. 2 февраля послы попросили от имени их государя руки Елены, старшей дочери великого князя, «чтобы, говорили они, заключить вечную дружбу и семейный союз на все времена». Выражения, увы, более пышные, чем справедливые! Ответ был, естественно, утвердительным и проникнутым набожной покорностью воле Провидения. Через четыре дня, 6 февраля, по случаю обручения послы видели Елену в первый раз. Накануне великий князь поставил условием, чтобы его дочь сохранила греческую веру и чтобы в деле религии она не потерпела никакого принуждения. Литовцы поклялись в этом своими головами.
Вскоре все значение этого обязательства выяснилось на одном случае, который не предвещал ничего доброго. Счастливый видеть наконец войну оконченной, Александр от всего сердца ратификовал все и позволил себе лишь легкое добавление в том, что касалось веры невесты; если Елена, прибавил он, пожелает по доброму желанию принять нашу римскую веру, она вольна это сделать. Это ограничение встретило энергичное сопротивление московских посланных, отправленных в Литву для обмена грамот. Они с ужасом отвергли примирительную редакцию Александра. Пришлось обратиться к самому Ивану, оказавшемуся в данном случае еще более неумолимым, чем его послы. Политика укрепляла православное рвение Ивана. Он поставил гордо такую дилемму: или разрыв брака, или устранение этого условия. Александр уступил вновь. 26 октября 1494 года он подписал собственной рукой и припечатал своим гербом грамоту, где, согласно московским требованиям, совершенно было выкинуто неприятное условие.
Когда эти уступки устранили последние препятствия, литовские послы, Ольханский и Забережский, прибыли в Москву в 1496 году за невестой. Празднества и пиршества не помешали Ивану окружить себя хитрыми предосторожностями. Он потребовал повторения брака, согласно греческим обрядам, по окончании латинской церемонии, устройства в Вильне православной церкви рядом с княжеским дворцом: произвольные притязания, послужившие впоследствии источником взаимных неудовольствий. В виде приданого Елена получила только строгий приказ о посещении греческих церквей; что касается до церквей латинских, то самое большее она могла их посетить раз или два из любопытства. Православная свита невесты не должна была торопиться своим возвращением и составить в Вильно постоянный двор. Иван снабдил их самыми подробными инструкциями насчет того, кому где сидеть, как одеваться, как делать визиты и устраивать обеды: от этого наставления не отказался бы китайский мандарин с красным шариком на шапочке.