Однако самым крупным строительством в Кремле было возведение кирпичных крепостных стен вместо изрядно обветшалых белокаменных времен Дмитрия Донского. Они неоднократно поправлялись, чинились, прикрывались деревянными заплатами, которых было так много, что один из иностранных путешественников записал, что кремлевские стены построены из дерева. В особенности пострадал Кремль в пожар 1445 г., когда 14 июля «загореся град Москва (внутри города, то есть в Кремле. – Авт.) в нощи и выгоре весь, яко ни единому древеси на граде не остатися, но и церкви каменые распадошася, и стены градные каменые падоша в многых местех, а людей множество изгоре…».
В 1451 г., когда ордынский царевич Мазовша приступил к Москве, оказалось, что во многих местах «несть крепости каменыя». Летописи и позднее сообщают о повреждении крепости: в 1473 г. «огоре граднаа кровля, и приправа вся городнаа», в 1479 г. при пожаре «бяху бо поварни за градом под стеною градною, и загореся поварни те, и от того кровля граднаа загореся».
Мысль о крепостных стенах конечно же занимала Ивана III. Сразу после восшествия на трон он занялся их поправлением. В 1462 г. великий князь указал перестроить стены на участке от Боровицкой до Свибловой башни. Руководил этим тот же Ермолин.
Однако совсем другой размах получили работы в Кремле после женитьбы Ивана III на племяннице императора Византии Зое Палеолог. Тогда Кремль в основном и приобрел современный вид.
Отец Зои, правитель провинции Морея (на полуострове Пелопоннес в Греции), брат последнего византийского императора Константина, Фома Палеолог, после падения империи бежал в Италию, где его гостеприимно встретил папа римский. После смерти Фомы заботу о Зое взял на себя ее опекун, кардинал Виссарион, радевший о восстановлении Византийской империи и воссоединении православной и католической церквей: он участвовал во Флорентийском соборе, где была одобрена «уния», то есть союз между двумя церквями. Виссарион пользовался в Италии большим влиянием и даже претендовал на избрание папой. Он был выдающимся ученым и способствовал знакомству Италии с греческой культурой; свою большую библиотеку завещал Венеции при условии свободного доступа. Виссарион понимал, что привлечение Русского государства к борьбе против турок может быть решающим для восстановления Византии, и непосредственно содействовал заключению брака Зои с русским великим князем. В 1469 г. в Москву прибыл грек Юрий с грамотой от кардинала Виссариона, в которой дочь морейского правителя Зоя Палеолог предлагалась в невесты. Великий князь, посоветовавшись с матерью, митрополитом Филиппом и боярами, отправил в Рим посла с поручением посмотреть предполагаемую невесту. Обратно тот привез ее согласие и портрет. Царевна, по словам очевидцев, была очень полной, невысокого роста, с красивыми глазами и удивительной белизной кожи, но, правда, внешние данные в этом политическом браке не играли главной роли.
Обсудив все еще раз, Иван отправил посольство с окончательным согласием на брак. Там, в Риме, в соборе Святого Петра в исключительно торжественной обстановке состоялось обручение Зои с великокняжеским уполномоченным, а затем она отправилась в неведомую страну. Путешествие длилось четыре месяца: сначала на север, к Балтийскому морю, потом на корабле к русским берегам. 12 ноября 1472 г. Зоя Палеолог въехала в Москву. Ее привезли в церковь под благословение митрополита, потом в хоромы матери великого князя, где жених и невеста впервые увидели друг друга. После обручения состоялось венчание в деревянной временной церкви, поставленной посреди строящегося Успенского собора. Итак, византийская принцесса Зоя Палеолог стала московской великой княгиней Софьей Фоминичной.
С появлением Зои Палеолог в Москве облик и обычаи великокняжеского двора значительно изменились: теперь уже никто и помыслить не мог обращаться к Ивану III со «многими поносными и укоризненными словами», как было возможно еще недавно. Существенно большее внимание уделялось пышности, богатству, церемонному этикету, появились придворные чины, был принят герб – двуглавый орел, который, согласно последним исследованиям, заимствовали из герба Священной Римской империи. Великий князь рассматривался как прямой преемник римских императоров и единственный охранитель истинной веры.