Одновременно с постройкой нового дворца началась реконструкция стен и башен Кремля, возведенного когда-то Дмитрием Донским. Руководить всеми работами поручили итальянским инженерам и зодчим во главе с Пьетро Антонио Солари. В помощь им пригласили мастеров-каменщиков из Ростова, Пскова, Твери и самой Москвы. Грандиозная работа продолжалась десять лет. В 1495 году перед москвичами во всей красе предстала суровая и величественная крепость, стены которой были украшены зубцами и снабжены бойницами. По углам возвышались круглые башни, у центральных, с проездными воротами, имелись отводные башни с опускавшимися решетками. Позднее со стороны Красной площади был выкопан широкий ров, через который к проездным башням перекинули подъемные мосты. В итоге Московский Кремль превратился в самую большую и неприступную крепость в Европе, великокняжескую резиденцию, достойную государя всея Руси и его царственной супруги.
Софья Фоминична привечала самых разных иностранных специалистов. Серебрянник Христофор с учениками занялись изготовлением украшений и дорогой посуды. Особенно порадовал ее приезд «органного игреца» монаха Иоанна. Он принял православие и женился на русской девушке. Вскоре в Москву был привезен и орган. Великая княгиня могла теперь наслаждаться его игрой, вспоминая о далекой родине.
Некоторые историки полагали, что роль Софьи Палеолог в кремлевских преобразованиях конца XV века была незначительной. И без ее участия Иван III сверг бы ордынское иго, стал самодержцем всея Руси и превратил Москву в настоящую столицу обширного Русского государства. С этим мнением можно согласиться лишь отчасти. Несомненно, могущество московских властителей росло постепенно, на протяжении нескольких столетий и ко времени Ивана Васильевича достигло кульминации. Это позволило великому князю вести самостоятельную внешнюю политику, не оказывать почтения и не платить дань золотоордынским ханам, активно бороться с вольнолюбивым Великим Новгородом и в конце концов присоединить его к своим владениям, окончательно сломить своих соперников, тверского и рязанского князей. Брак же с Софьей Палеолог лишь ускорил естественный ход событии и придал им новый характер.
Можно предположить, что Софье, как наследнице императорского престола, не нравилось, что ее муж все еще официально считался ханским улусником и должен был унижаться перед ордынцами. Так, в июле 1476 года она с удивлением увидела, как ее гордый супруг водил за узду коня ханского посла Бочюкая, почтительно кланялся ему и т. д. Надменный ордынец всячески демонстрировал свою власть над великим князем и требовал все больше и больше дорогих подарков для хана Ахмата. Напоследок он заявил, что Иван Васильевич должен ехать в Орду за ярлыком на великое Владимирское княжение.
Софья Фоминична не стала осуждать поведение мужа при ордынских послах. Но, будучи тонким политиком, с хитрым и гибким умом, она сумела намеками убедить Ивана Васильевича окончательно порвать с Золотой Ордой. Ведь для этого у него имелось все необходимое: крепкие стены Кремля, отважное, хорошо вооруженное войско, достаточно надежные союзники.
Вряд ли бывшая византийская принцесса, сама испытавшая ужас нашествия «безбожных агарян», была сторонницей открытой схватки с ханом Ахматом. Она считала, что достаточно создать крепкий заслон на границах Русской земли. Великий князь придерживался того же мнения и организовал на окском береговом рубеже пограничную службу.
Летом 1480 года разведчики донесли, что к Москве движутся многочисленные орды хана Ахмата. Это известие повергло Софью Фоминичну в ужас. Сразу вспомнились ее детские страхи перед неверными и бегство из Морей в Италию. Возможно, она боялась не столько за себя, сколько за своих маленьких детей. К этому времени она родила двух дочерей и двух сыновей, младшему Юрию не было и года.
В панике Софья Фоминична потребовала, чтобы муж укрыл ее с детьми в безопасном месте. На этот раз выбрали Белоозеро, а не традиционную Кострому. Вместе с великой княгиней отправили и казну, которая помогла бы ей бежать в европейские страны в случае разгрома Москвы. Сборы были поспешными. С собой брали только все самое необходимое и наиболее ценное. Вскоре москвичи с удивлением могли наблюдать, как кортеж великой княгини покидает столицу.
У многих современников ее бегство вызвало осуждение. Ведь враг находился далеко, и непосредственной угрозы для Москвы не было. Даже престарелая княгиня Мария Ярославна, вдова Василия Темного, никуда не собиралась ехать, старший сын великого князя, Иван Молодой, желал возглавить полк, а сам Иван III повел свое многочисленное войско к Оке.
Не любившие «грекиню» бояре стали открыто заявлять, что все беды страны именно от нее и ее окружения: «Как приехала царевна со своими князьями, так вся земля наша и замешалася». В случае гибели государя они вряд ли позволили бы Софье Фоминичне вернуться в Москву и вновь поселиться в Кремле.