Первоначально на этом месте планировалось возвести общественную богадельню, для нужд которой в 1859 г. по Высочайшему повелению предоставили часть места упраздненной Обойной фабрики с каменной казармой мастеровых, принадлежавшей с 1780-х гг. фабрике ассигнационных бумаг. Проект перестройки казармы под богадельню с домовой церковью разработал И. А. Монигетти, в 1863-1865 г. велось строительство под руководством А. Ф. Видова, но затем его приостановили в связи с нехваткой средств. В 1869 году городу было Высочайше разрешено перепрофилировать здание в мужскую гимназию. Наименование Николаевской было присвоено в память императора Николая Павловича и скончавшегося цесаревича Николая Александровича, о чем извещалось в тексте памятной доски, помещенной на фасаде. 8 сентября 1870 года в Городовой Ратуши состоялся торжественный акт открытия гимназии в присутствии Александра II и августейших особ. Гимназия прославилась своими педагогами и воспитанниками, среди которых можно назвать поэта И. Ф. Анненского, возглавлявшего гимназию и проживавшего здесь с 1896 г. по 1905 гг. Воспитанниками гимназии были Н. Н. Гумилев, В. А. Комаровский, В. А. Рождественский, Н. Н. Пунин и многие другие.

Г. В. Семенова Александр II, император
Анненский Иннокентий Федорович
Видов Александр Фомич
Гумилев Н. Н.
Комаровский Василий Алексеевич, гр.
Монигетти Ипполит Антонович
Николай I, император
Пунин Николай Николаевич
Рождественский Всеволод Александрович
Набережная ул./Пушкин г., д. 12