В феврале 1469 года посланец кардинала Виссариона Никейского, опекуна Зои, — разумеется, с одобрения папы Павла II — прибыл в Москву предлагать руку царевны из династии Палеолог. Дело оказалось не быстрым — князь Иван хотел посоветоваться со своими боярами и матерью, княгиней Марией Тверской, а затем отправил в Рим служившего при его дворе выходца из Италии, Джана Батистту делла Вольпе, прозванного на Руси Иваном Фрязином. Тому надлежало вести переговоры с папой и кардиналом, а также посмотреть на невесту. Тот не только посмотрел, а и привёз, вернувшись в ноябре 1469 года, её портрет, дело неслыханное при московском дворе. Однако переговоры затянулись, и только в январе 1472 году Вольпе отправился в Италию во второй раз, уже непосредственно за невестой. Он и сопровождавшие его русские бояре прибыли в Рим в мае.
Сохранилось описание Зои тех времён. Правда, заметим, оставил его флорентийский поэт Луиджи Пульчи, сопровождавший в Рим красавицу Клариссу Орсини, супругу Лоренцо Медичи — желая позабавить Лоренцо Великолепного и, весьма вероятно, противопоставить византийскую царевну своей госпоже, Пульчи высказался весьма резко: «Мы вошли в комнату, где торжественно восседала эта толстуха, и уверяю тебя, ей было на чём восседать… Два турецких литавра на груди, отвратительный подбородок, лицо вспухшее, пара свиных щёк, шея, ушедшая в эти литавры. Два глаза, стоящие четырёх, и с таким количеством жира и сала кругом, что никогда ещё реку По не запруживала лучшая плотина. И не думай, что ноги её походили на ноги Юлия Постника…» Поэт уж чересчур злоязычен, и, заметим, по его же собственному признанию, сама Кларисса была очарована внешностью Зои и сочла её красавицей. К тому же работы по восстановлению внешнего облика Зои Палеолог доказывают, что черты лица у неё были чёткие, правильные, глаза действительно большие, ну а полнота… уж что-что, а тогда дородность на Руси недостатком не считалась, а выйти замуж ей предстояло именно там. Так что оставим это описание на совести остряка — если судить по остальным сохранившимся описаниям современников, это не портрет, а карикатура. Но именно его, увы, любят часто цитировать, забывая упомянуть, что недовольство Пульчи могло быть вызвано и тем, что в гостях у Палеологов флорентийца не угостили так, как он, должно быть, рассчитывал…
1 июня 1472 года в пышно разукрашенной базилике Святого Петра состоялась торжественная церемония. На ней присутствовали королева Боснии Катерина со своими спутницами, Кларисса Орсини, знатные патрицианки Рима, Сиены и Флоренции. Вероятно, были там и греческие соотечественники Зои. Во время обручения оказалось, что кольца невесты русская сторона не припасла — как объяснил Вольпи, у них нет такой традиции. Так что пришлось, по всей видимости, воспользоваться наспех взятыми у кого-то кольцами.
От папы римского Сикста IV (сменившего скончавшегося Павла) Зоя получила подарки и приданое шесть тысяч дукатов. В своём труде, посвящённом союзу Зои и Ивана III, «Царское бракосочетание в Ватикане» П. Пирлинг описывает фреску в Санто-Спирито, «показывающую нам Зою на коленях перед папой, а рядом с нею равным образом на коленях измышление художника поместило жениха; они оба имеют на голове короны, а папа, по бокам которого стоят Андрей Палеолог [брат Зои] и Леонардо Токко, даёт кошелёк Зое».
Кроме того, «королеве русской» предоставили и приличествующую её происхождению и новому сану свиту, а в те места, которые она должна была проезжать на пути в Москву, были направлены соответствующие письма. Так, герцог Модены получил от Сикста IV следующее послание: «Наша возлюбленная во Христе Иисусе дщерь, знатная матрона Зоя, дочь законного наследника константинопольской империи Фомы Палеолога, славной памяти, нашла убежище у апостольского престола, спасшись от нечестивых рук турок во время падения восточной столицы и опустошения Пелопоннеса. Мы приняли её с чувствами любви и осыпали её почестями в качестве дщери, предпочтённой другим. Она отправляется теперь к своему супругу, с которым она обручена нашим попечением, дорогому сыну, знатному государю Ивану, великому князю Московскому, Новгородскому, Псковскому, Пермскому и других, сыну покойного великого князя Василия, славной памяти; мы, который носим эту Зою, славного рода, в лоне нашего милосердия, желаем, чтобы её повсюду принимали и чтобы с ней повсюду обращались доброжелательно, и настоящим письмом увещеваем о Господе, твоё благородие, во имя уважения, подобающего нам и нашему престолу, питомицей коего является Зоя, принять её с расположением и добротой по всем местам твоих государств, где она будет проезжать; это будет достойно похвалы и нам доставит величайшее удовлетворение».