24 июня 1472 года, простившись с папой в садах Ватикана, Зоя направилась на далекий север. Будущая великая московская княгиня, лишь только очутившись на русской земле, еще находясь на пути под венец в Москву, коварно предала все надежды папы, немедля забыв все свое католическое воспитание. Софья, по-видимому, встречавшаяся в детстве с афонскими старцами, противниками подчинения православных католикам, в глубине души была глубоко православной. Она сразу же открыто, ярко и демонстративно показала свою преданность православию, к восторгу русских прикладываясь ко всем иконам во всех церквах, безукоризненно ведя себя на православной службе, крестясь, как православная. Планы Ватикана сделать принцессу проводником католичества на Русь потерпели провал, поскольку Софья немедленно продемонстрировала возвращение к вере предков. Папский легат был лишен возможности въехать в Москву, неся перед собой латинский крест.

Ранним утром 21 ноября 1472 года Софья Палеолог прибыла в Москву. В тот же день в Кремле во временной деревянной церкви, поставленной около строящегося Успенского собора, чтобы не прекращать богослужений, государь обвенчался с ней. Византийская принцесса впервые тогда увидела своего супруга. Великий князь был молод – всего 32 года, хорош собой, высок и статен. Особенно замечательными были его глаза, «грозные очи». И прежде Иван Васильевич отличался крутым характером, а теперь, породнившись с византийскими монархами, он превратился в грозного и властного государя. В том была немалая заслуга его молодой жены.

Софья стала полноправной великой княгиней Московской. Сам факт, что она согласилась поехать искать счастья из Рима в далекую Москву, говорит о том, что она была смелая, энергичная женщина.

Она привезла на Русь щедрое приданое. После венчания Иван III принял герб византийского двуглавого орла – символ царской власти, поместив его и на своей печати. Две головы орла обращены на Запад и Восток, Европу и Азию, символизируя их единство, а также единство («симфонию») духовной и светской власти. Приданым Софьи была легендарная «либерия» – библиотека (больше известная как «библиотека Ивана Грозного»). Она включала в себя греческие пергаменты, латинские хронографы, древневосточные манускрипты, среди которых были неизвестные нам поэмы Гомера, сочинения Аристотеля и Платона и даже уцелевшие книги из знаменитой Александрийской библиотеки.

По преданию, она привезла с собой в подарок мужу «костяной трон»: его деревянный остов весь был покрыт пластинами из слоновой и моржовой кости с вырезанными на них сюжетами на библейские темы. Софья привезла с собой и несколько православных икон.

С приездом в 1472 году в столицу России греческой принцессы, наследницы былого величия Палеологов, при русском дворе образовалась довольно большая группа выходцев из Греции и Италии. Многие из них заняли со временем значительные государственные должности и не раз выполняли важные дипломатические поручения Ивана III. Все они возвращались в Москву с большими группами специалистов, среди которых были архитекторы, врачи, ювелиры, мастера монетного дела и оружейные мастера.

Великая грекиня принесла с собой свои представления о дворе и могуществе власти. Софья Палеолог не только произвела перемены при дворе – некоторые московские памятники обязаны ей своим возникновением. Многое из сохранившегося ныне в Кремле было построено именно при великой княгине Софье.

В 1474 году Успенский собор, возводимый псковскими мастерами, рухнул. К восстановлению его были привлечены итальянцы под руководством зодчего Аристотеля Фиораванти. При ней выстроили церковь Ризположения, Грановитую палату, названную так по случаю отделки ее в итальянском стиле – гранями. Сам Кремль – крепость, охранявшая древний центр столицы Руси – рос и создавался на ее глазах. Спустя двадцать лет иностранные путешественники стали именовать Московский кремль по-европейски «замком», ввиду обилия в нем каменных строений.