На возвратном пути синьор Джан Батиста заехал в Венецию, где был встречен с большим почетом, и посулил сенату республики провести в Золотую Орду дипломатического агента, который должен был договориться с ханом о выставлении против турок войска в 200 тысяч всадников. Отправляясь в дальнейший путь, он включил в свиту своего племянника Антонио Джисларди, состоявшего на дипломатической службе Венецианской республики, и секретаря венецианского сената Жана Батисту Травизиана, скрыв его истинный статус и назвав другим своим племянником, который едет по торговым делам.
В Москву посольство Ивана Фрязина вернулось в 1471 году, доставив князю Ивану рисованный на доске портрет принцессы Зои-Софии и подробный отчет о переговорах. К моменту возвращения посольства в Москве стало известно, что умер папа Павел II, но точно не знали, кто занял ватиканский престол после него. Во всяком случае, со свадьбой решили не тянуть, и Ивану Фрязину приказано было опять собираться в путь — 16 января 1472 года он снова выехал в Рим во главе посольского каравана. Из-за такой спешки при подготовке княжеской свадьбы переправить венецианца Травизиана в Орду он не успел, и тот остался в Москве вместе с Антонио Джисларди, чтобы дождаться возвращения делла Вольпе с княжеской невестой.
К концу мая 1472 года делла Вольпе добрался до Рима, где выяснилось, что грамота, которой его снабдили в Москве, по недостатку верных сведений была написана на имя папы Калликста, а понтификом стал Сикст IV. Тем не менее русский посол был принят, предстал перед тайной консисторией и, несмотря на изъян верительной грамоты, смог достойно объясниться. Тут очень пригодились дорогие подарки, поднесенные папе, — синьор делла Вольпе вручил его святейшеству шубу из драгоценных северных мехов и в добавок к тому семьдесят соболей, что произвело самое благоприятное впечатление на понтифика. Разрешение на брак Зои Палеолог и русского князя Ивана было дано, дело пошло по накатанной стезе, причем княжескому послу пришлось символически заменить персону своего господина во время обряда обручения с невестой. Пышная церемония состоялся 1 июня в базилике Св. апостолов Петра и Павла, куда Зою-Софию сопровождала пышная свита.
Папа Сикст 24 июня 1472 года принял Зою в ватиканских садах, и во время этой прощальной аудиенции поднес ей щедрые подарки, а сверх того пожаловал в приданое шесть тысяч дукатов. В тот же день она навсегда покинула Рим. С нею в Москву ехал папский легат, епископ Антон Бонумбре, которому было поручено склонить московских правителей и церковных иерархов к принятию унии.
Огромный караван княжеской невесты проследовал от Рима к Флоренции, оттуда в Сиену, далее в Болонью, Виченцу, на Нюрнберг, и всюду на его пути местные власти устраивали триумфальные шествия и праздники, длившиеся по нескольку дней. По немецким землям они проехали до Любека, где сели на корабли, которые доставили их в Ревель, а оттуда в Дерпт.
К границе русских земель караван принцессы Палеолог приблизился 11 октября 1472 года. Едва ступив на русскую землю, принцесса иначе как Софьей не звалась. Она демонстративно подчеркивало свое православие и весьма резко одернула епископа Бонумбре, выказавшего пренебрежение православным иконам. В Пскове встречали ее торжественно и радостно, но там путешественники не задержались, отправившись в Новгород, а оттуда в Москву, куда прибыли 12 ноября.
Сразу же по приезде принцесса Софья отправилась в Успенский собор, который тогда перестраивался, и отслужила молебен. Из храма она прошла в кремлевский терем матери жениха, вдовствующей великой княгини Марии Ярославовны, и там впервые увидела своего суженого. Через несколько часов после первой встречи коломенский протопоп Осия повенчал их в деревянном шатре, устроенном внутри недостроенного собора. Еще неделю спустя, 18 ноября, в далекой Равенне скончался кардинал Виссарион, и тем самым оборвалась последняя связь супруги великого князя с римской юностью. Началась новая жизнь — гонимая принцесса-сирота Зоя стала Софьей Фоминичной, великой княгиней Московской.
