Проект создали П.Д.Готман и И.Е.Ефимов (утвержден 19 апреля 1835 г.), надзор за работами осуществлял архитектор А.Л.Леер. В 1837 г. были заложены фундаменты и возведены вчерне стены. Но в 1838 г. А.Л.Леер вступил в конфликт с губернатором и был отставлен от дел. Работы продолжили архитекторы А.И.Шеффер и А.Е.Турмышев, отделку интерьеров осуществил подрядчик - тверской ямщик И.Т.Дубицкий, меблировал столяр Н.Е.Волков.

На исходе 1841 г. в Санкт-Петербург сообщалось о завершении строительства. В ансамбль вошли главное трехэтажное здание, флигель, корпус кардегардии, арсенал и общественный сад. Поставленное над обрывом Кремлевского холма здание из-за оползней грунта получило вскоре повреждение. В 1846 г. инженер А.И.Дельвик, заливая трещины в фундаментах и сводах подвалов, впервые в строительной истории Н.Новгорода применил бетон. Крупные ремонты проводились в 1885 и 1894-1896 гг., когда по проекту архитектора Н.И.Иванова был выполнен металлический зонт на чугунных столбах парадного входа и овальные пандусы подъездов.

Здание связано с именами многих известных людей: декабристов А.Н.Муравьева и И.А.Анненкова, романиста А.Дюма. В 60-х гг. 19 в. А.О.Карелин и Л.В.Даль открыли здесь первую в Н.Новгороде общедоступную художественную школу.