Кривцов и Мышкин приступили к разборке старой церкви, которая была на три метра меньше вновь возводимой и потому оказалась внутри. Летописи сообщают, что там же была сооружена временная деревянная церковь, в которой и происходило венчание Ивана III с принцессой Софьей.

В 1474 г. стены были выведены под своды, но вдруг в мае обрушилась северная стена, внутри которой находилась лестница на хоры, и часть западной. Все надо было начинать заново. Были срочно вызваны псковские мастера для консультаций. Они похвалили «гладкость» стен, но заявили, что известь, употребленная для постройки, недостаточно «клеевита», т. е. не обладает необходимой вязкостью для закрепления каменных блоков. От участия в постройке они отказались.

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

На самом деле все объяснялось проще. Кривцов и Мышкин, как и псковские мастера, не строили таких обширных храмов, какой предстояло воздвигнуть в Кремле. Монгольское нашествие прервало строительные традиции Киевской и Владимиро-Суздальской земель, некогда давших непревзойденные образцы зодчества. Необходимо было восстановить эти традиции, но на основе современной строительной техники. В этом был смысл приглашения итальянцев на Русь.

Собор простоял полуразрушенным в течение года. А в 1475 г., сразу же по приезде в Москву, Аристотель приступает к строительству. По летописям можно почти год за годом восстановить порядок работ. У исследователей вызывает разногласие только время поездки Фиораванти по городам Северо-Восточной Руси — Владимир, Новгород, Псков, куда он отправился для ознакомления с памятниками древнерусского зодчества и прежде всего с Успенским собором во Владимире. Есть основания думать, что он дважды совершил это путешествие: в первый раз — в сравнительно близкий от Москвы Владимир, затем, уже позднее, — на север.

Фиораванти не счел возможным включить в свое сооружение уцелевшие части старой церкви, и работы начались с разрушения ее остатков. Делалось это удивительным для москвичей способом. Так называемый «баран» — тяжелое дубовое бревно, окованное железом и подвешенное между тремя брусьями, связанными верхними концами, раскачиваясь взад и вперед, со страшной силой ударяло в стену и разрушало ее. Летописец записал о впечатлении, произведенном этим устройством: "…еже три года делали, во едину неделю и меньше развали".

Прежде чем приступить к рытью фундамента и кладке стен, Фиораванти тщательно выяснил причины падения Успенской соборной церкви. Он подтвердил точку зрения псковских мастеров о непригодности известкового раствора и показал, как надо его готовить. В результате "известь же густо мотыками повеле мешати, и яко наутрие же засохнет, то ножем не мочи расколупити… как тесто густое растворяше, а мазаша лопатками железными".

По свидетельству летописи, фундамент был заложен на глубине свыше двух саженей, причем укладывался он не на грунт, а на дубовые сваи, забитые в основание рва. Это все были новшества, удивлявшие москвичей, но быстро воспринятые ими.

Русские строители применяли кирпич и до приезда Фиораванти, но он был плохого качества и шел главным образом для забутовки белокаменных стен. Аристотель построил специальные кирпичные заводы за Андрониковым монастырем в Калитникове, на берегу Москвы-реки. По сравнению со старым русским кирпичом новый был более продолговатой формы и неизмеримо более твердым.

Закончив подготовительные работы (разрушение старой церкви, рытье рвов для фундамента и заготовка кирпича), Фиораванти в том же 1475 г. приступил к кладке стен. Предварительно он съездил на древние разработки белого камня в Мячково под Москвой, опробовал камень и наладил его доставку на строительную площадку.

Летопись сообщает, что в тот же год стены вышли из земли, но клали их по-другому. Вместо битого кирпича и мелкого камня, служивших для забутовки, теперь между наружными и внутренними белокаменными стенами клали кирпич, заготовленный по размеру и рецепту Фиораванти. Это было проще, быстрее, и главное, что нагрузка при этом ложилась не на облицовку, а на кирпичную кладку, которая, собственно, и была стеной. Тогда же начали ставить внутренние столбы. Всего их шесть: четыре — круглых, два — квадратных, скрытых алтарной преградой. На них опираются двенадцать крестовых сводов. Это тоже было новостью, ибо древняя форма столба квадратная, с вырезанными четырьмя углами, образующими в плане равноконечный крест.

В 1476 г. Аристотель выводит стены на высоту аркатурно-колончатого пояса. Для крепости он употребляет вместо традиционных дубовых связей металлические, закрепляя их анкерами на наружных стенах. Для подачи кирпича и извести использовались подъемники. Летопись подробно останавливается и на этих нововведениях.

В 1477 г. собор был вчерне закончен. Еще два года ушло на внутреняюю отделку, и 15(26) августа 1479 г. Успенский собор был торжественно освящен.

Уже современники смогли оценить красоту нового собора. Автор Воскресенской летописи записал: "Бысть же та церковь чюдна велми величеством и высотою и светлостью и звонкостью и пространством; такова же прежде того не бывало в Руси, опричь Владимирска церкви; а мастер Аристотель".