Больше года вдовец оставался неутешен — с Марией он был обручен с детства и прожил в счастливом браке пятнадцать лет. Но потом по совету митрополита и бояр стал подумывать о новой женитьбе.
В феврале 1469 года в Москву прибыло посольство из Рима. Это было достаточно необычным явлением, поскольку тесных связей с католическими странами русские князья не поддерживали. Во время приема грек Юрий Траханиот передал Ивану III письмо от кардинала Виссариона. Великому князю предлагалось жениться на византийской царевне Зое Палеолог, племяннице двух последних императоров и дочери морейского деспота (правителя) Фомы.
Решив заинтересовать великого князя, хитрый кардинал отметил, что царевна уже отказала двум женихам, французскому королю и миланскому герцогу, из-за нежелания менять православную веру на католическую.
На деле, как полагали современники, возможные претенденты на руку Зои отказались от нее сами, узнав о ее непомерной толщине и отсутствии приданого. Но разве это могло стать препятствием для Ивана III? Тучность женщины на Руси всегда считалась признаком красоты, а приданым в великокняжеской среде обычно были небольшие подарки жениху (пояс и т. д.) и личные вещи невесты. Ценились лишь знатность и обширные родственные связи будущей жены.
В этом же отношении Зоя Фоминична Палеолог была исключительно подходящей кандидатурой для Ивана Васильевича, желавшего стать государем всея Руси и навсегда свергнуть золотоордынское иго. Своей знатностью она поднимала престиж мужа, а родственными связями могла способствовать установлению контактов со многими европейскими державами, потенциальными союзниками в борьбе с Ордой.
После визита Юрия Траханиота Иван III созвал совет, на который пригласил митрополита Филиппа, мать — Марию Ярославну, видных бояр. Сообща решили, что византийская царевна может претендовать на роль новой великой княгини. Дело со сватовством откладывать не стали и вскоре отправили в Рим посольство во главе с Иваном Фрязином, итальянцем, приглашенным в Москву для организации монетного дела. На родине его звали Джан Баттист Деллавольпе.
Миссия русского посольства оказалась успешной. Иван Фрязин был принят Римским папой и кардиналом Виссарионом, с которым довольно быстро договорился об условиях предполагаемого брака. Католики надеялись, что женитьба на Зое убедит
Ивана III присоединиться к Флорентийской унии и тем самым подчинит православное духовенство Римскому папе.
Русский посол был представлен Зое, получил ее портрет и «опасные» грамоты, позволяющие проезжать без всяких препятствий через католические страны.
В конце того же 1469 года Иван Фрязин вернулся в Москву. Портрет византийской царевны произвел на всех большое впечатление, ведь до этого никто не видел изображения людей в реальном облике. Летописцы даже назвали его иконой.
Внешность невесты, скорее всего, понравилась великому князю: огромные карие глаза, черные брови, нос с горбинкой, полный рот. Взгляд спокойный и твердый. Именно так выглядит византийская царевна на скульптурном портрете, воссозданном по ее останкам экспертом-криминалистом С. А. Никитиным. Правда, это изображение дает представление о женщине пятидесяти с лишним лет.
Исследование скелета показало, что рост Зои не превышал 160 сантиметров и что она страдала некоторыми гормональными нарушениями. Они выразились в том, что под конец жизни Зоя очень располнела, черты лица стали более грубыми, появились небольшие усики и волоски на подбородке. Вызвать их могли стрессовая ситуация в детстве и резкая смена климата после переезда из Рима в Москву.
Привезенный великому князю портрет царевны не сохранился. Нет и других достаточно достоверных описаний ее внешности. Из исторической литературы известно лишь о том, что Зоя была изображена на фресках собора Сан-Спирито, посвященных жизни папы Сикста IV. На одной из них она на коленях получала от папы свадебный подарок —- кошелек с 6000 дукатов, на другой — царевна среди знати во время благословения ее братьев Сикстом IV. Но, по мнению исследователей, эти фрески были поздними и вряд ли передавали реальный облик Зои. Кроме того, в настоящее время они в плохом состоянии.
Некоторое представление о внешности византийской принцессы могут дать воспоминания о ней очевидцев-современников. Патрицианка Клариса Орсини, встречавшаяся с ней в Риме, в своих записках назвала Зою красивой. Итальянские хронисты описывали ее так: невысокого роста, с удивительно красивыми большими глазами и кожей несравненной белизны.
Многие отмечали ее благонравие, ласковое обхождение с гостями и способности к рукоделию.