Имея перед глазами образец Московского Кремля, возведенного отцом, великий князь Василий III пожелал возвести цепь аналогичных твердынь на границах Московского княжества. Этот тип крепостей характерен для Ломбардии, столицей которой является славный град Милан, откуда на службу русским князьям приехало немало мастеров и разного рода умельцев. В 1508 году были начаты работы в Нижнем Новгороде, где под руководством архитектора Пьетро Франческо к 1515 году была возведена мощная крепость с тринадцатью боевыми башнями. В 1521 году было закончено строительство кремля в Туле, а четырьмя годами позже начались работы в Коломне. Как предполагают, строительством коломенской крепости распоряжалась команда итальянских мастеров, которыми руководил опытный зодчий Алевиз Фрязин, которого звали Алевиз Новый, так как до его приезда в Москве работал миланский архитектор Алевиз де Каризано, прибывший сюда еще в 1494 году.
Алевиз Новый отправился в Московию десятью годами позже своего миланского тезки и коллеги в составе очередной группы итальянских мастеров, которая сопутствовала русским послам, возвращающимся из Италии. Они добрались морским путем до Крыма, где их некоторое время удерживал хан Менгли-Гирей, предложивший поработать на строительстве Бахчисарайского дворца. В июне 1503 года хан писал Ивану III: «Нонеча слава Богу, на свои руки взял есми Дмитрия Ларева да Митрофана Федорова Карачарова; и мастеры твои иуня месяца к нам приехав и челом ударили. Мастеры фрясские и с женами и с детьми и с девками к нам пришли». Помянутые в ханском послании «Ларев» и «Карачаров» — это послы князя Ивана III, Дмитрий Ралев и Митрофан Федорович Карачаров, посланные в 1499 году в Венецию «о княжьих потребах». Там они навербовали «серебряных, пушечных и сенных дел мастеров», в числе которых был и архитектор Алевиз. Посол при ханском дворе боярин и воевода Алексей Григорьевич Заболоцкий в своем донесении уточнял дату прибытия посольского каравана с итальянскими мастерами — до ханской столицы они добрались «за две недели до Петрова Заговенья», то есть не позже первых дней июня. В Бахчисарае посольство задержалось до сентября 1504 года, и за этот в принципе короткий срок — всего за год — архитектор Алевиз успел выстроить для хана прекрасный Бахчисарайский дворец. Отпустив после настоятельных просьб ожидавшихся в Москве мастеров, хан, на тот момент московский союзник, премного довольный работой Алевиза, так писал о нем «брату своему князю Ивану»: «Меня брата твоего ярлык взяв, пошел Алевиз мастер, вельми доброй мастер, не как иные мастеры, вельми великий мастер… То как меня почтишь и мое брата своего слово почтишь, того фрязина Алевиза пожалуешь, ты ведаешь». Архитектор вполне оправдал столь лестную аттестацию.
