В 1813 году был объявлен официальный конкурс на проект храма, в итоге среди различных проектов, представленных на усмотрение государя в процессе международного соревнования, внимание Александра I привлекла работа молодого художника Александра Лаврентьевича Витберга. 12 октября 1817 года, через пять лет после того, как французы оставили Москву и бросились бежать из России по Калужской дороге, произошла торжественная закладка храма на Воробьевых горах в присутствии императора Александра Павловича. Закладка была совершена весьма торжественно, особенно запомнились многим слова архиепископа Августина: «Где мы? Что мы видим? Что мы делаем?» Как оказалось впоследствии, слова эти были пророческими.
Но проект этот осуществлен не был, в т. ч. и по объективным причинам – неподходящего для возведения столь грандиозного сооружения грунта, невозможности доставки строительных материалов по Москве-реке. В затянувшийся процесс постройки храма не раз вмешивался государь, сначала Александр I, затем сменивший его в 1825 году Николай I. Строительство на Воробьевых горах остановилось, зато начался суд над архитектором, руководившим постройкой храма. Летом 1835 года долгое разбирательство закончилось. Все бывшие под судом лица во главе с Витбергом были признаны виновными «в злоупотреблениях и противозаконных действиях в ущерб казне». В покрытие государственного долга (строительство обошлось более чем в четыре миллиона рублей!) все имущество осужденных было реквизировано и продано с торгов. В том же 1835 году Витберга отправили в ссылку в Вятку.
Еще 19 февраля 1830 года министр императорского двора сообщал московскому генерал-губернатору Дмитрию Голицыну: «Его Императорское Величество приказал, чтобы князь Голицын собрал всех архитекторов и спросил, согласны ли они строить храм на Воробьевых горах, если нет, тогда уже избрать места и составить конкурс из русских архитекторов и заграничных». Таким образом, возникла необходимость не только в новом обоснованном проекте храма, но и в выборе другого места под его строительство. Новое место для храма было избрано самим Николаем I – рядом с Кремлем, на берегу Москвы-реки, где находился до того времени Алексеевский женский монастырь. Здания монастыря предполагалось разобрать, а сестер монастыря перевести в Красное село. Современники так оценили выбор царя: «Место для постройки избрано самим Государем на возвышении берега Москвы-реки, ввиду величественного Кремля – Палладиума нашей народной славы». Он же выбрал и нового зодчего – Константина Андреевича Тона.
10 сентября 1839 года на Волхонке состоялась новая закладка храма, за которой и наблюдал Лев Толстой: «В сей день с утра первопрестольный град пришел в движение. Светлый осенний день благоприятствовал торжеству. На месте закладки выстроен был великолепный павильон». Это свидетельство очевидца, благодаря которому мы можем себе представить, что же видел будущий писатель. Сама церемония указывала на огромное, государственное значение факта закладки храма, недаром само мероприятие началось с Успенского собора Кремля: «К 10-ти часам утра все лица, назначенные к участию в церемонии, собрались в Успенском соборе. По окончании литургии вся церемония вышла с молебным пением из южных врат, обогнула Ивановскую колокольню и заняла свои места близ большого колокола».
Космический масштаб церемонии восторженно воспринимался москвичами. Один из свидетелей происходящего, Федот Кузмичев, так вспоминал появление царя: «Наконец, после долгого ожидания, раздались голоса командующих: смирно! На плечо! Барабаны забили, звуки музыкальных инструментов раздавались вместе с гулом ура! И пронеслись по всему фронту. Вот наш Батюшка несется на борзом коне. За ним Государь Наследник, Его Высочество Михаил Павлович… Ну слава Богу, теперь дождемся великой церемонии закладки Храма, в память избавления России в 1812 году».
Процессия, выйдя на Красную площадь через Никольские ворота, двинулась затем по набережной через Ленивку к месту закладки храма. Затем «Государь Император, приближаясь к месту заложения, благоволил высыпать в выдолбленное там укрепление приготовленные для сего отечественные монеты чекана 1839 года… Главный архитектор (Константин Тон – А.В.) представил Государю Императору на серебряном золоченом блюде плитку с именем Его Величества, а также золоченую лопатку с молотком; в то же время каменный мастер поднес на другом серебряном блюде известь. Император, приняв плитку, благоволил положить оную в выдолбленное место, а подле с левой стороны приложил и другую плитку с именем Государыни Императрицы».