6 января 1491 года была сооружена Спасская башня Московского кремля

В правление Дмитрия Донского в восточной части крепости располагалась белокаменная Фроловская башня с железными воротами. При ремонте 1464—1466 годов архитектор Василий Ермолин украсил стены сооружения рельефами с изображением святых Георгия Победоносца и Дмитрия Солунского. Тем не менее земляные работы вокруг башни не проводили, поэтому устройство несущих конструкций доподлинно неизвестно. Во время московского пожара 1488 года сгорели деревянные настилы трёх ярусов боя башни и пушечная изба поблизости.

В период правления Ивана III приступили к масштабной реконструкции крепости, возведение её восточной части начали со строительства новой Фроловской башни. Летописные свидетельства подтверждают, что её построили на месте старой башни или в непосредственной близости от неё. Работами руководил архитектор Пьетро Солари, об этом свидетельствуют белокаменные плиты с памятными надписями, установленные над въездными воротами башни. С внешней стороны надпись сделана на латинском языке, с внутренней — на славянском:
В лето 6999 [1491 год] июля божией милостию сделана бысть сия стрельница повелением Иоанна Васильевича государя и самодержца всея Руси и великого князя Володимерского и Московского и Новгородского и Псковского и Тверского и Югорского и Вятского и Пермского и Болгарского и иных в 30 лето государств его, а делал Пётр Антоний Солярио от града Медиолана.

Строительство завершилось в 1491 году. Основание сооружения представляло собой четырёхгранник с проездной аркой, прикрытой с внешней стороны отводной стрельницей и двумя боковыми бастионами.

Стрельница — кирпичная пристройка с аркой в нижней части — использовалась для защиты проездных ворот. При необходимости проход перекрывали железными решётками — герсами, и неприятель оказывался запертым внутри. Стрельница была открыта сверху, что позволяло обстреливать врага с галереи второго этажа. Для этого наверху располагались зубцы с бойницами. Такая система защиты характерна для военной архитектуры конца XV века и была устроена на всех проездных башнях Кремля. Фроловская башня считалась главной среди кремлёвских фортификационных сооружений, её венчал деревянный шатровый купол, под которым разместили часовой и набатный колокола. Железные затворы Фроловских ворот с двух сторон расписали «по золоту цветами». Для безопасного передвижения воинов в толщине крепостных стен проложили проходы. Галерею, связывавшую Фроловскую и Набатную башни, позднее заложили каменными ядрами.

В правление Василия III между Москвой-рекой и Неглинной вдоль стен крепости проложили Алевизов ров. От Фроловских ворот через водоток перекинули деревянный подъёмный мост. Вскоре из-за оживлённого движения его заменили арочным каменным и стали именовать Спасским. На мосту регулярно выставляли лубочные картинки, на подходах стояли нищие, калеки и слепые.