Президент Академии художеств А. Н. Оленин предложил использовать предстоящие работы по строительству и отделке дворца как практическую школу для воспитанников Академии. Руководить двенадцатью архитекторами, скульпторами и художниками был назначен А. П. Брюллов – родной брат живописца Карла Брюллова. Главным распорядителем всех работ назначался Стасов. Ему же поручалось «возобновление дворцового здания вообще, наружная его отделка и внутренняя отделка обеих церквей и всех зал». Общее руководство работами Николай поручил все тому же Клейнмихелю. И тот со своей задачей справился, разумеется, не без большой пользы для себя.

Через несколько дней вокруг уцелевших от огня кирпичных стен дворца начали ставить строительные леса, через 3 недели уже воздвигли временную кровлю, и одновременно с этим начали самым интенсивным образом очищать внутренние залы дворца от золы, пепла, мусора и обгоревших трупов.

Офицер-преображенец Дмитрий Гаврилович Колокольцов, очевидец и участник этих событий, писал через 45 лет, что в очистке дворца участвовали «все гвардейские полки беспромежуточно, по крайней мере, с месяц времени… Находили иных людей как заживо похороненных, других обезображенных и покалеченных. Множество трупов людей обгорелых и задохшихся от дыма было усмотрено почти по всему дворцу». (Справедливости ради следует сказать, что всем родственникам погибших Николай приказал выплачивать пенсии).

Когда мусор вывезли, а трупы похоронили, во дворец шли 2000 каменщиков и начали возводить стены, колонны, потолки и лестницы. А вскоре на строительство и отделку дворца каждый день выходили 6000-8000 человек. Стены, перекрытия и кровля дворца были возведены необычайно быстро, и без всякого промедления начались внутренние отделочные работы. Главной задачей было интенсивное и эффективное осушение только что воздвигнутых, совершенно сырых помещений. Для этого поставили 10 огромных специальных печей, непрерывно обогреваемых коксом, и 20 вентиляторов с двойными рукавами, выведенными в форточки. Все это, прогревая помещения и выкачивая сырость и вредные пары от красок, клея и других химических веществ делало воздух в помещениях сухим и чистым, поддерживало температуру на уровне +36 °C.

И все же де Кюстин, побывавший в Зимнем дворце сразу же после его второго рождения, писал: «Во время холодов от 25 до 30° шесть тысяч неизвестных мучеников, мучеников, не заслуживших этого, мучеников невольного послушания были заключены в залах, натопленных до 30° для скорейшей просушки стен. Таким образом, эти несчастные, входя и выходя из этого жилища великолепия и удовольствия, испытывали разницу в температуре от 50 до 60°. Мне рассказывали, что те из них, которые красили внутри самых натопленных зал, были принуждены надевать на голову шапки со льдом, чтобы не лишиться чувств в той температуре. Я испытываю неприятное чувство с тех пор, как видел этот дворец, после того, как мне сказали жизней скольких людей он стоил. Новый императорский дворец, вновь отстроенный, с такими тратами людей и денег, уже полон насекомых. Можно сказать, что несчастные рабочие, которые гибли, чтобы скорее украсить жилище своего господина, заранее отомстили за свою смерть, привив своих паразитов этим смертоносным стенам, уже несколько комнат дворца закрыты, прежде чем были заняты».

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

А Петр Андреевич Клейнмихель 29 марта 1839 года был возведен в графское Российской империи достоинство с пожалованием девиза «Усердие все превозмогает».