Первоначально на этом месте в 1788 году была возведена деревянная церковь.В 1792 году её разобрали и перенесли за пределы города на кладбище, где она была вновь собрана и освящена во имя святых мучеников Флора и Лавра.На освободившемся участке в 1793 году началось строительство новой каменной двухэтажной церкви.
К 1796 году завершилось строительство нижнего храма, который был освящён в честь святителя Николая, архиепископа Мирликийского Чудотворца. Верхний храм был достроен и освящён в 1802 году в честь Рождества Пресвятой Богородицы. В 1845 году к основному зданию были пристроены двухэтажные каменные приделы с южной и северной сторон. Южный придел включал нижний храм во имя Рождества святого Иоанна Крестителя и верхний храм в честь Тихвинской иконы Божией Матери. Северный придел содержал нижний храм, посвящённый святому пророку Илии.
В 1932 году, в период антирелигиозной политики советского государства, собор был закрыт. Здание использовалось для различных нужд: здесь размещались общежитие агропедагогического техникума, мастерские зерносовхоза, в годы Великой Отечественной войны — Московское политическое училище и школа младшего командного состава, а после войны — автомеханический техникум.
