Меньше чем через два года после смерти Марьи Борисовны великий князь задумал вновь жениться. К этому представился очень благоприятный случай. В 1469 году приехал к великому князю грек Юрий с письмом от римского кардинала Виссариона, который предлагал Ивану Васильевичу руку греческой царевны Софьи Палеолог.
Царевна Софья была дочь Фомы Палеолога. Этот Фома Палеолог, после падения Византии, когда брат его, последний византийский император из дома Палеологов, Константин, погиб на стенах своей столицы, искал со своим семейством убежища в Риме, где он уже имел родственные связи, потому что женат был на дочери герцога Феррарскаго. Следовательно, Софья Палеолог была гречанкой по отцу и итальянкой по матери. Софья, после смерти Фомы Палеолога, осталась с двумя братьями. Папа Павел II принял молодую царевну под свое покровительство, конечно с целями воспользоваться ею в видах распространения своего духовного владычества и на того государя, с которым, как он справедливо мог надеяться, Софья соединить свою судьбу. Ничего лучше нельзя было желать для папы, как распространить свою власть на обширные земли вновь восходившего на востоке сильного светила – царства московского, на которое римские первосвященники уже несколько столетий смотрели с завистью, и потому самым подходящим для этого орудием папа признал молодую царевну, которой мать была католичка по рождению; да и сама она, прожив несколько лет в Риме, не могла не подпасть под некоторое влияние искусной католической пропаганды, хотя и была рождена и воспитана сначала в греческой вере. Нужно было для этого во что бы то ни стало выдать Софью за московского великого князя, и потому папа для переговоров с ним избрал посредником кардинала Виссариона, бывшего греческим митрополитом, подписавшим в числе других духовных представителей восточной церкви, флорентинскую унию. Предлагая Софью в замужество великому князю, кардинал Виссарион между прочим сообщил Ивану Васильевичу, что царевна из ревности к греческой вере отказала уже двум женихам, французскому королю и медиоланскому герцогу.
Иван Васильевич, говорит летописец, взял эти слова в мысль и, посоветовавшись с митрополитом Филиппом, с боярами, в марте же месяце отправил в Рим посла Ивана Фрязина, выходца из Италии, служившего при великом князе монетным мастером.
Фрязин оказался хорошим сватом, как для той, так и для другой стороны. С одной стороны папе хотелось приобрести в великом князе московском сильного союзника против страшных турок, которые в то время уже ступили своей тяжелой пятою на европейский материк, раздавив этою пятою древнюю и славную некогда Восточную или Византйско-Римскую империю, затем при посредстве Софьи и своих легатов, воздействовать на Ивана Васильевича к восстановлению флорентийской унии. Вообще планы папы в этом отношении могли быть очень широкими и надежды очень радужными, притом же, по-видимому, и сбыточными. С другой стороны, московский князь, уже ощущавший под собою почву самодержавия, так как прежние уделы почти не существовали, а Тверь, Новгород, Псков и даже Орда начинали уже чувствовать тяжелую руку «московского господаря», искал более прочного укрепления в умах идеи самодержавия, а это укрепление возможно было в перенесении московским князем на свою особу нравственного наследия византийской империи: это наследие могло принести с собою представительница императорского рода в Византии, утратившего свою империи. Идея византийской империи, таким образом, как бы переносилась на Москву, на плечи московского самодержавного князя.
Фрязин, как ловкий проходимец, которому, однако в Риме охотно верили, быстро выполнил свое посольство и воротился в Москву с портретом царевны, а равно с «опасными» (проезжими, пропускными) грамотами от папы для беспрепятственного следовая по всем католическим землям московских послов в Рим за царевною и обратно, когда будет совершен обряд обручения, хотя бы заочного.
Вскоре в Рим отправлено было посольство за невестой, и Фрязин назначен был от великого князя представлять лицо жениха при церемонии обручения, как это водилось в то время и как это мы увидим ниже, при обручении дочери Ивана Васильевича, Елены, выходившей замуж за князя литовского Александра.
В июне 1472 года царевна выехала из Рима. Ее сопровождал кардинал Антоний и немалое число греков. Ехала она морем и вступила на русскую землю выше Пскова.
Вот любопытное описание, по летописцу, встречи, которую приготовили царевне псковичи: