Первая жена Ивана III княгиня Мария Тверская умерла в 1467 г. Она родила ему в 1456 г. сына Ивана Молодого, который около 1470 г. получил титул великого князя и был признан как соправитель своего отца. Оставшись с одним маленьким сыном, Иван III скорее всего беспокоился о безопасности наследования трона. Предложения второго брака шли, возможно, молодому правителю с разных сторон (ко времени кончины Марии Ивану было двадцать семь). Факт того, что второй брак последовал не сразу, а спустя пять лет после первого, может свидетельствовать о верности Ивана III памяти своей первой супруги. Кроме того он был не из тех, кто принимает быстрые решения: весьма возможно, что он решил подождать удобной возможности жениться на иностранной княжне. Подобный брак, как можно утверждать, должен был поднять значимость московского правителя и поставить его самого и его семью над местной московской аристократией. Такой брак мог быть полезен и с точки зрения дипломатии и международных отношений.
Возможность вскоре представилась. В 1468 г. Джан Баттиста делла Вольпе (известный в Москве как Иван Фрязин), итальянец, которого Иван III сделал ответственным за чеканку монет в Москве, послал в Италию двух агентов — итальянца Никколо Джис-лярди (или Джилярди) и грека Георгия (Юрия). Их основной задачей было привлечение итальянских техников для Ивана III.20 Агенты Вольпе были приняты в Риме папой Павлом II, который решил использовать их для начала переговоров о женитьбе Ивана III на византийской принцессе Зое Палеолог, племяннице византийского императора Константина XI. Семья Зои приняла декларацию Флорентийской унии, и сама Зоя стала римской католичкой. Папа являлся ее опекуном. В феврале 1469 г. (дата русских летописей) грек Юрий вернулся в Москву с итальянскими техниками, братом Вольпе Карло и Антонио Джислярди (Антоном Фрязиным). Юрий также доставил Ивану письмо от кардинала Виссариона — наставника Зои — с предложением ее руки.
Подготавливая брак Зои и Ивана, папа имел двоякую цель поддержать римский католицизм в России и сделать великого князя московского своим союзником против османских турок. Опасаясь османского владычества, папа (равно как и венецианский сенат) собирал любых возможных союзников, включая властителей Золотой Орды и Ирана. Агенты Вольпе, скорее всего преувеличивая силу Московии, дали папе совершенно ложное представление о желании Ивана III воевать с турками. Сам Вольпе лелеял собственный амбициозный план — стать главным агентом папы и Венеции на востоке. Для достижения этого он не возражал против обмана как папы, так и великого князя московского, если это могло служить его собственным планам.21 Когда он прибыл в Московию, то согласился обратиться в греческое православие, но тайно оставался римским католиком. Теперь он уверил московитов, что Зоя была греко-православной. В то же время он дал папе основание верить, что католическое исповедание Зои не будет препятствием для вступления Зои в брак с Иваном III.
После получения послания Виссариона, Иван III посоветовался со своей матерью, а также митрополитом Филиппом и боярами. С их одобрения он послал Вольпе в Рим в 1470 г. для того, чтобы обсудить это дело с папой Павлом и кардиналом Виссарионом. Зоя согласилась выйти замуж за Ивана, а папа и кардинал одобрили ее выбор. Вольпе привез в Москву портрет Зои. Зимой 1471-1472 гг. возможность брака была вновь обсуждена Иваном III и его советниками. Окончательное решение было принято. 16 января 1472 г. Вольпе еще раз отправился в Рим, чтобы привезти № Москву невесту Ивана. (Папа Павел умер в 1471 г. Новость достигла Москвы до отъезда Вольпе, но имя нового папы было извращенно передано как «Калист». Это имя было впоследствии упомянуто в официальном письме Ивана III папе. Однако, когда Вольпе и его спутники достигли Италии, то им сообщили, что имя нового папы Сикст, а не Калист. Вольпе нашел легкий выход из трудной ситуации: он стер в письме Ивана неправильное имя и вписал верное).
24 мая 1472 г. московские посланцы были приняты папой Сикстом IV. 1 июня в Ватикане состоялась торжественная церемония — помолвка Зои с Иваном III (Вольпе выступал в роли доверенного лица великого князя московского). Некоторые историки называют эту церемонию свадьбой, а не помолвкой. П. Перлинг предпочитает говорить о ней, как о «свадьбе Ивана в Ватикане». Однако он признает, что документы неоднозначны.22 Фактически же Перлинг сам цитирует письмо папы герцогу Модены от 21 июня 1472 г., в котором папа говорит, что Зоя недавно «стала невестой» Ивана.23
24 июня Зоя, сопровождаемая папским легатом Антонио Бонумбре, Вольпе, греком Дмитрием Ралевым (Ралли, который должен был представлять братьев Зои на свадьбе в Москве), другим греком Юрием Траханиотом (которого русские хроники называют «боярином») и многочисленной свитой, направилась из Рима через Флоренцию и Нюренберг в Любек. Здесь Зоя и ее свита взошли на корабль, который доставил их в Ревель (по-русски — Колывань) 21 октября. Морское путешествие заняло одиннадцать дней. Маршрут, который должна была избрать Зоя, является хорошей иллюстрацией хаоса, сопряженного с сообщением между Италией и Восточной Европой, который стал результатом османского завоевания Константинополя и Балкан. Как морской путь из Италии к Черному морю, так и наземный путь через Польшу и Литву были блокированы турками. Из Нюренберга Зоя могла избрать сухопутный маршрут через Польшу и Литву, но как раз в это время отношения между Иваном III и королем Польши и Литвы Казимиром были натянутыми из-за новгородского конфликта. К тому же дороги через Литву были очень плохи, в особенности осенью.
Из Ревеля Зоя и ее свита проехали к Пскову, где духовенство, бояре и все население приветствовали ее. Хотя Зою сопровождал папский легат, она, очевидно, захотела расположить русских к себе, приняв их обычаи и веру, еще до начала путешествия. Это могло быть результатом совета боярина Юрия Траханиота, который, согласно псковской летописи, был родственником епископа тверского.24 Поэтому перед въездом в Псков Зоя надела русские царские одежды и в Пскове без консультации с папским легатом посетила собор Святой Троицы и поклонилась иконам. Легат, оказавшийся в затруднительном положении, тем не менее последовал за Зоей в Москву. Здесь он по обычаю шел за служителем, который нес то, что русский летописец поименовал «латинским крестом» (распятие). Это чуть не послужило причиной конфликта, поскольку митрополит Филипп ожесточенно возражал против публичной демонстрации латинского креста в Москве и угрожал покинуть город. Несмотря на возражения Вольпе, легату запретили нести распятие перед ним.