Строительство каменного кремля в Коломне началось 25 мая 1525 года по инициативе Великого князя Василия III и продолжалось шесть лет. Кремль возводился с внешней стороны деревянной стены и представлял собой многоугольник, близкий к овалу, с периметром стен почти 2 км, что всего на 300 м меньше длины стен Московского Кремля. Толщина стен составляла 3-4,5 м, а высота, 18-21 м. Они были облицованы кирпичом с каменной забутовкой внутри и оснащены бойницами для различных видов боя. Стены завершались зубцами, на которых крепились ставни для защиты. Количество башен менялось в разные периоды, но кремль имел как минимум 13 башен и шесть ворот: три "больших", Пятницкие, Ивановские, Косые и три "малых", Малаховские, Георгиевские, Водяные. Северо-западный и северо-восточный углы крепости защищали мощные Коломенская и Свиблова башни. Свиблова башня, самая высокая и мощная, контролировала течение Москвы-реки и дорогу к Пятницким воротам. Её высота достигала 34,6 м, а диаметр, 13,8 м. Коломенская башня, высотой 34,4 м, контролировала дорогу Москва-Рязань и украшена декоративными машикулями. С ней связано предание о Марине Мнишек, из-за чего её называют "Маринкиной". Главный въезд в кремль осуществлялся через Спасские, или Пятницкие ворота, представлявшие собой трёхярусную башню с дозорной вышкой. Ивановские ворота на юго-западе кремля напоминали Пятницкие и также имели решётки-герсы. Грановитая башня на юге от Коломенской башни была пятиярусной и шестигранной снаружи. На восточной стороне находились четырёхгранные башни: Ямская, Спасская и Погорелая. На западной стороне между Свибловой и Коломенской башнями, вероятно, располагались шесть башен, не сохранившихся до наших дней. Водяные ворота выходили на Москву-реку, рядом находилась Тайницкая башня с подземным ходом к воде. Косые ворота имели Г-образный проход и располагались на Косой горе. Мельничные ворота вели к мельнице на противоположном берегу Коломенки и имели надвратную башню, позже разобранную. Между Грановитной и Коломенской башнями находилась проездная арка Малаховских ворот, заложенная во второй половине 16 века.

В августе 1531 года строительство кремля было завершено. Построенный по образцу Московского, он лишь немного уступал ему. К 17 веку, когда границы государства переместились на юг, крепость утратила оборонительное значение. В 1606 году город захватили войска Ивана Болотникова, а в Смутное время он неоднократно подвергался разграблению польско-шведских захватчиков. Тем не менее Коломна полностью оправдала своё предназначение, став символом неприступности русского государства. Степные враги ни разу не смогли в открытом бою овладеть этой крепостью, служившей надёжным щитом Москвы с юга.