Итак, взойдя на крутой берег Москвы-реки, откуда открывалась прекрасная панорама Белокаменной, Николай I огласил решение о необходимости выстроить здесь свой дворец. Не зря Пушкин в стихотворении «Стансы», написанном вскоре после памятной встречи с Николаем I в 1826 году, сравнил его с великим реформатором: «И академик, и герой, и мореплаватель, и плотник». Конечно, Николай I самолично не рубил струги в древней царской вотчине, но ему очень хотелось походить на Петра. Коломенское должно было послужить своеобразной демонстрационной площадкой.
Прежний царский дворец Евграфа Тюрина в стиле московский ампир совершенно не вписывался в концепцию государственной идеологии николаевского царствования, сформулированной министром народного просвещения Сергеем Уваровым в 1833 году: «Россия не может благоденствовать, усиливаться, жить без таковых начал, как: 1) Православная Вера. 2) Самодержавие. 3) Народность». Нужен был новый дворец, внушавший очевидное мнение, что «прошлое России удивительно, настоящее прекрасно, будущее же выше всяких представлений» (слова Александра Бенкендорфа). Нужен был и новый архитектор, в поиске кандидатуры которого особых проблем не возникло. Николай словно вынул приготовленный ранее козырь из кармана, назвав фамилию Андрея Штакеншнейдера, ученика Огюста Монферрана, автора многих петербургских дворцов и царских резиденций. Крупнейшая фигура в истории градостроительства Северной Пальмиры, Штакеншнейдер создал проекты Мариинского, Николаевского, Ново-Михайловского дворцов, а также дворца Белосельских-Белозерских. Он строил в Петергофе, Царском Селе, Стрельне. Иными словами, именно усилиями Штакеншнейдера создавался так знакомый нам образ дворцового Санкт-Петербурга середины XIX столетия.
И вот теперь этот видный зодчий, совершенно не чувствовавший Москвы (возьмем на себя смелость так сказать), вдруг ни с того ни сего принялся проектировать дворец для Коломенского. А истинно московского зодчего Евграфа Тюрина отставили, поручив ему «доставить фасад церкви Вознесения и цены на материалы для архитектора Штакеншнейдера по составляемому им проекту перестройки Коломенского дворца». Можно представить переживания Тюрина, который теперь должен был заняться подготовкой к сносу своего дворца.
Штакеншнейдеру, судя по процитированному отрывку, некогда было самому детально разбираться во всякого рода строительных подробностях. Фасад храма Вознесения необходим был ему, поскольку он не придумал ничего лучше, как включить древнейшую церковь в свой проект. Мало того, на правом фланге будущего дворца должна была вознестись точная копия храма Вознесения, образовав таким образом симметричную композицию. Кому-то это показалось варварством, но не Штакеншнейдеру, умело заправлявшему свои эклектичные проекты элементами самых разных стилей – классицизма, готики, ренессанса, барокко, древнерусского зодчества. Как бывалый повар готовит сборную солянку из всего, что есть под рукой, так и Штакеншнейдер использовал в своем проекте Коломенского дворца доставленный ему фасад храма Вознесения.
Созданный на бумаге архитектурный ансамбль был представлен Николаю I в 1836 году и получил высочайшее одобрение. Штакеншнейдер настолько угодил царю, что тот даже рекомендовал использовать стилистическую основу Коломенского дворца при разработке проекта другой императорской резиденции – Большого Кремлевского дворца, которым занимался в то время Константин Тон. Это означало более чем высокую оценку усилий Штакеншнейдера, поскольку Тон считался основоположником собственного стиля – русско-византийского.
Вторая половина 1830-х годов – это время интенсивного строительства в Москве, кроме Большого Кремлевского дворца, на Волхонке в тот период началось возведение многострадального храма Христа Спасителя по проекту того же Тона. Первая попытка строительства храма на Воробьевых горах завершилась неудачей и стоила казне огромных и зря понесенных расходов, за что к уголовной ответственности привлекли архитектора Александра Витберга. Неудивительно, что Николай I смотрел, как говорится, в оба за тем, как идет строительство и куда направляются государственные деньги. Проект Штакеншнейдера стоил больше, чем возведение Большого Кремлевского дворца и храма Христа Спасителя, вместе взятых. Даже при условии использования кирпича от недостроенного Царицынского дворца, вероятность чего рассматривалась. Поэтому очевидным явилось решение о некоторой отсрочке начала строительства в Коломенском.
Но, как известно, то, что объявлено временным, обладает всеми признаками постоянства. Строительство храма на Волхонке затянулось, став одним из самым длинных за всю историю наблюдений: храм был освящен лишь в 1883 году. Дворец в Кремле отстроили раньше, к 1849 году.