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