В 1895 г. учреждена женская прогимназия им. графини А.А. Евдокимовой (1825-1895) – вдовы генерал-адъютанта Н.И. Евдокимова. Сын солдата Николай Иванович Евдокимов (1804-1873) стал видным кавказским военным деятелем, генералом от инфантерии и генерал-адъютантом, графом. Герой Кавказской войны, с чьим именем связано ее завершение в 1864 г., кавалер всех отечественных орденов и других высоких наград был удостоен права быть похороненным в ограде Спасского храма. Графиня завещала открыть прогимназию в своем доме, который передавался городскому управлению. Кроме того, она завещала содержать прогимназию на проценты от своего капитала в 75 тысяч рублей. В свою очередь городская дума обязывалась выделять ежегодно на содержание этого учебного заведения из городского бюджета около 2 тыс. руб. Попечителем прогимназии стал душеприказчик графини известный в городе доктор медицины Карл Андреевич Барт. Членами попечительского совета были известные в городе люди, в том числе священник М. Закхеев, купец С. Зипалов. В 1898 г. четырехклассная прогимназия была преобразована в пятиклассную прогимназию, в 1899 г. — в шестиклассную, в 1902 г. — в гимназию.

 

В 1914 г. в гимназии обучалось 333 ученицы, педагогический персонал — 20 человек, среди которых были классные дамы. Они занимались воспитанием гимназисток, прививали им хорошие манеры, навыки учтивости, соблюдение обязательной формы одежды — темно-зеленого шерстяного платья и черного фартука, по праздникам — белого. После окончания девушки могли работать в городской начальной школе или поступать на высшие женские курсы.