И снова Ивану III пришлось созывать совет. Снова были высказаны мнения о том, что великому князю не нужна невеста-«римлянка», однако Иван III уже принял решение — жениться именно на ней.
В Москве не любили спешить в серьезных делах. Иван III отправил в Рим «к папе и гардиналу Васариону» послов во главе с Иваном Фрязиным за Софьей только через несколько месяцев, 16 января 1472 года. В ходе подготовки посольства произошел конфуз. Русские знали, что 28 июня 1471 гола умер папа Павел II. Однако в имени нового папы они допустили ошибку, назвав его в краткой верительной грамоте Калистом. Уже в дороге послам стало известно настоящее имя нового папы — не Калист, а Сикст. Они вышли из положения с наивной простотой, исправив в грамоте имя папы: «а тот прежней папа Павелъ умре, а сказали, что инъ папа Калистъ именем. Вшедшим же в землю ту и слышаша папино имя Систюсь, а не Калистъ, и о том мысливше меж себя преписаша, имя того Калистово выгладивъ, Систюша написаша».>{264}
Можно предположить примерный маршрут движения московского посольства в Рим. Согласно летописным данным, «Иван III дал… Ивану Фрязину специального проводника пана Юргу с ним в провожатех, что знает путь тот идти на Новгород, и оттуду к Риму».>{265} Иван Фрязин «со товарищи» отправился по старинной торговой дороге через Новгород и Балтику до Любека, а затем по немецким землям на юг. Эта дорога в ту пору была не очень известна русским. Она начала активно использоваться только после покорения Новгорода, с рубежа 1470–1480-х годов. Именно поэтому русскому посольству и потребовался провожатый. Надо думать, что москвичам много пришлось претерпеть на этом пути. Помимо прочих опасностей, надо было не один день проходить через альпийские перевалы.
И все же этот северный путь был менее опасен, чем южный, которым несколько веков подряд пользовались итальянские купцы в своих сношениях с Русью. В XIII–XIV столетиях, в пору расцвета торговых факторий Генуи и Венеции в Северном Причерноморье, «фряжские» купцы традиционно ходили на Русь морским путем через Крым и Черное море. Этим маршрутом возвращались на родину и русские представители на Ферраро-Флорентийском соборе. Однако в начале 1470-х годов южная дорога стала весьма неприветливой: турки, захватившие Византию, стремились контролировать и Черное море. В 1475 году ими будет захвачена венецианская Каффа (современная Феодосия). К тому же Иван III имел весьма натянутые отношения с правителем Большой Орды ханом Ахматом.
Существовал и третий путь из Италии на Русь. Он проходил через Смоленск, Вильно, Варшаву, Познань. Этой дорогой ездил в Рим с первым посольством Иван Фрязин, о чем свидетельствует сохранившееся папское бреве польскому королю от 1470 года. Однако к 1472 году русско-литовские отношения осложнились, и этим путем русское посольство пользоваться также не могло.