В январе следующего, 1495 года новое литовское посольство приехало в Москву за невестой. Отслушав обедню в Успенском соборе, Иоанн торжественно, в присутствии своего семейства и бояр, передал дочь Елену литовским послам. На дорогу он снабдил ее подробным наказом, как она должна вести себя в чужой земле; причем особая забота опять посвящалась вопросу вероисповедному. «В латинскую божницу не ходить, — подтверждал наказ, — а ходить в свою церковь; захочет посмотреть латинскую божницу или монастырь, то может посмотреть один раз или дважды. Если будет в Вильне королева, мать Александрова, ея свекровь, и если пойдет в свою божницу, а ей велит идти с собою, то Елене провожать королеву до божницы и потом вежливо отпроситься в свою церковь, а в божницу не ходить». Условлено было, чтобы венчание происходило тотчас по прибытии невесты в Вильну. Но по приезде сюда сопровождавшие Елену московские бояре, с князем Семеном Ряполовским и Михаилом Русалкой во главе, тщетно настаивали, чтобы это венчание совершилось в православной церкви и русским владыкой. Великая княжна направилась сначала в церковь Рождества Пречистой, где ее встретил архимандрит Макарий, возведенный в сан западнорусского митрополита, и отслужил молебен. Княгиня Марья, жена Семена Ряполовского, и жена Русалки, по московскому обычаю, расплели ей косу, причесали голову, возложили на нее кику и покрывало и осыпали ее хмелем; сопровождавший Елену священник Фома прочел молитвы и благословил ее крестом. Отсюда она отправилась в католический собор Св. Станислава, где ее ожидал великий князь Александр. Под ноги великой княжны подостлали кусок бархата и сорочек соболей. Венчальный обряд совершал латинский епископ. Тут дело не обошлось без столкновения. Священник Фома, стоя около невесты, начал вполголоса говорить ей молитвы; княгиня Марья Ряполовская держала над ней венец, а дьяк Кулешин имел наготове сткляницу с вином. Епископ пытался их отстранить, но князь Семен настоял на выполнении приказа Иоанна. Фома дал Елене выпить вина; после чего сткляницу бросили на землю и растоптали, по русскому обычаю. Радея об исполнении своих обычаев, московские бояре потом поставили на вид Александру и то обстоятельство, что на следующий день после венчания у него «не было мыльни».
Этот брачный союз не только не скрепил заключенного перед тем мира, но скоро послужил источником новых неудовольствий. Обе стороны увидели свои надежды обманутыми: Александр думал с помощью жены обеспечить свои земли от всяких притязаний со стороны тестя; а Иоанн рассчитывал посредством дочери и ее будущих детей иметь влияние на Литовскую Русь.
Первым поводом к неудовольствию и жалобам послужил все тот же вероисповедный вопрос, в котором московская ревность к православию натолкнулась на такую же ревность католическую. Иоанн изъявил желание, чтобы для дочери его была построена особая «церковь Греческаго закону на переходех подле ея хором», то есть при виленском дворе. Александр отвечал, что по привилегиям, данным земле его, он обязался не прибавлять в ней греческих церквей и что в городе есть близко греческая церковь, куда его княгиня может ходить свободно. Иоанн хотел, чтобы при Елене оставалось несколько московских бояр и детей боярских, пока она привыкнет к чужой стороне; Александр вскоре отослал их обратно; причем писал тестю: «У нас, слава Богу, слуг много; есть кому служить нашей великой княгине». Иоанн оскорблялся подобными ответами и продолжал настаивать на построении особой придворной церкви, но безуспешно. Этого мало: до великого князя Московского доходит слух, что его зять, подчиняясь внушениям папы Александра VI, начал понуждать свою супругу к переходу в католичество. Иоанн посылает сказать дочери, что пусть лучше она пострадает и примет смерть, чем изменит православию.