Ивану Васильевичу на момент смерти жены было 27 лет. К Великому князю поторопился папский посол с предложением жениться на Софье. Предложения были и из других дворов Европы. Но Иван Васильевич был честолюбив и возможность жениться на внучке императора Византии, православного центра, ему польстила. Случилось это в 1469 году. Великий князь возжелал увидеть Софью, посол, грек Юрий, пообещал доставить парсуну с её изображением. Вместе с греком в Рим отбыл посол Ивана Васильевича именем Иван Фрязин. Кстати, коварные латиняне благоразумно умолчали, что Софья приняла католицизм. Папа римский принял Фрязина, папский двор даже дал ему разрешение ходить два года безвозбранно по землям, которые папству присягли. Фрязину вручили художественный портрет Софьи. Иван сверил, схож ли портрет с оригиналом, сходство его удовлетворило, с чем и отбыл в Москву. Софье тогда было 14 лет. Невысокая, 160 см ростом, миловидная брюнетка. Когда Фрязин показал Великому князю по прибытии в Московию портрет, был шок. Не было на Руси в те времена светской живописи. Бояре и сам Иван Васильевич приняли портрет за икону. Лик Софьи Великому князю понравился, и он дал согласие. Переговоры шли три года, всё же расстояние от Москвы до Рима большое, сношение происходило посольствами, на лошадях.
Уже первого июня 1472 года в базилике Святых епископов Петра и Павла в Риме состоялось заочное обручение Ивана III и Софьи Палеолог. Папа римский дал приданого шесть тысяч золотых дукатов. Высокопоставленных гостей было много, не каждый день бывают династические браки. Невесте на тот момент едва исполнилось 17 лет. Великого князя представлял Иван Фрязин. Не мешкая, выехали большим обозом. В свите Софьи Юрий и Дмитрий Траханиот, князь Константин, Дмитрий как посол её братьев – Андрея и Мануила, Косспан Грек, папский легат Антоний Бонумбре и епископ Агчии, а также слуги. А ещё на нескольких возах библиотека, которая в дальнейшем станет основой для библиотеки Ивана Грозного, внука Софьи.
Маршрут пролегал через север Италии в Германию. Обычно оттуда ехали сухопутным путём через Польшу. Но, поскольку у Казимира IV были с Иваном Васильевичем отношения натянутые, даже враждебные, в порту Любек Ганзейского союза, куда прибыли первого сентября, погрузились на корабль.
Одиннадцать дней плыли по Балтике и вы-грузились в Колывани. Снова обозом к Чудскому озеру, где на берегу их уже встречали псковские бояре и любопытный народ. Софью и всех людей из обоза переправили на лодьях через озеро, привезли в Псков, где встретили как дорогих гостей. Софья отдыхала всего сутки, хотя путь был утомительный. Но следовало поторапливаться, начиналась осень с её дождями. А Русь не Рим с его мощёными дорогами. Следующим городом был Великий Новгород. Ещё республика, но гнул его под себя Иван Васильевич. Партия сторонников Москвы Софью встретила торжественно. И вновь на отдых один день. Софья хоть и молода была, понимала – следует поторапливаться. Обручённая невеста ещё не жена, не венчана. Одно обручение у неё уже было, браком не закончившееся.