Для придания стене «вязкости», чтобы лучше противостоять огню осадной артиллерии, ее строили слоями: между двух кирпичных кладок оставляли пустоту, которую, по мере возведения кирпичной основы, закладывали бутовым камнем и заливали известковым раствором, приготовленным по рецептам итальянцев; этот раствор быстро «схватывал» камень, придавая конструкции прочность монолита. Стены выводили под углом, чтобы ядра теряли пробивную силу из-за рикошетирования. Фундамент башен выложили из больших каменных блоков, а стены возвели целиком кирпичные — они «держали» огонь пушек за счет толщины и особенностей конструкции.
Предположительно уже в ходе работ к мастерам присоединился еще один итальянский инженер, некий Пьетро Франческо Аннибале или, как его звали русские, «Петрок Фрязин», носивший звание «архитектона» — то есть «старшего архитектора». Кроме него «архитектонами» в русских документах значились Пьетро Антонио Солари (умер в 1493 году) и Алевиз Новый. Остальных мастеров-строителей (включая Аристотеля Фьораванти) звали «муролями», «палатными мастерами», «каменными (и плотницкими) старостами».
Архитектоны были сведущи в самых разных областях. Кроме умения делать чертежи и рисунки будущих сооружений они должны были составлять сметы и руководить работами. Для этого им необходимо было изучать строительную механику, знать химию и физику. На них лежали заготовка строительного материала и выбор строительной площадки, а значит, архитектон должен был знать геологию, минералогию и «всякое землемерие», как тогда называли геодезические работы. В добавление к этому «обязательному набору архитектона» Пьетро Аннибале был еще классным артиллеристом и военным инженером. При строительстве крепости в Коломне был использован элемент «бастионной системы» — Грановитая башня была полностью вынесена за пределы стены, благодаря чему расширились секторы обстрела вдоль стены и рва. Многогранник укрепления с артиллерийской батареей на верхней площадке с тыла имел прямоугольный каземат для хранения огневых припасов. Отличие Грановитой башни от классических бастионов и бастий заключалось в том, что они строились открытыми, а она имела несколько крытых ярусов.
Начавшиеся в 1525 году работы двигались очень споро, несмотря на то что шли фактически в зоне боевых действий. В 1527 году на Русь пожаловал со своим войском крымский хан Ислям-Гирей I, которого встретили под Коломной, в двадцати верстах от Оки. Простояв пять дней лагерем и узнав от разведчиков, что татары далее Зарайска не пошли, князь Василий приказал идти к окским бродам. Перейдя реку с войском, князь напал на крымчаков на берегах реки Осетр и погнал их прочь.
Война не только не мешала строительству новой крепости, а может быть, даже и подхлестнула ретивость строителей, управившихся с делом всего за шесть лет — в 1531 году готовая крепость по своему обводу имела десять четырехугольных башен-«бойниц», каждая высотой по одиннадцать саженей (почти 24 метра), да три «кольцевые» башни с двойными стенами, внутри которых имелись лестницы, ведшие в казематы и к боевым площадкам, защищенным кирпичными зубцами с раздвоенными вершинами типа «ласточкин хвост»; в зубцах были сделаны бойницы. Эти башни выступали за линию крепостной стены, что позволяло обстреливать с трех сторон разом противника, штурмующего стены.
Особо сильно укреплены были воротные башни. Спасская с главными проездными воротами была в высоту 13 саженей (28 метров), внутри она разделялась на четыре яруса. Над воротами имелась площадка для пушек. На стены прямо из башни можно было выйти по двум каменным лестницам. Проезды в Спасской башне с каждой стороны закрывали металлические ворота и решетки, которые при помощи механизма поднимались и опускались по специальным пазам. На самом верху башни была звонница с колоколом, звон которого поднимал гарнизон по тревоге. Со стороны Посада и слобод крепость окружал глубокий ров, через который у проездных ворот были перекинуты деревянные мосты. На Ивановской проездной башне была укреплена «закладная доска» со следующей надписью: «Город Коломна в первых начат строением в 7033 году майя в 25 день повелением благоверного государя и великого князя Василия Иоанновича, самодержца всея России, а совершен в 7038 году августа в 15 день». В данном случае слово «город» означает «крепость».
