На месте часовни Рождества Богородицы в 1766 году построена деревянная Рождественская церковь. В 1778 году построен новый храм. В 1791 году церковь сгорела от удара молнии. В 1795 году на площади Старого базара построена каменная церковь во имя Рождества Пресвятой Богородицы. С 1822 года храм соборный, освящение состоялось 20 апреля 1822 года.

Новый каменный собор построен в 1854-1860 годах. По проекту областного войскового архитектора Антона Кампиони. Колокольня построена рядом с собором в 1875-1878 годах, освящена 22 октября 1878 года, в день Казанской иконы Божией Матери в 8 часов утра перед Литургией.

В 1929 году с куполов сняты кресты. В 1937 году собор закрыт. Здание храма использовалось под склады и зернохранилище. Во время войны, при наступлении немцев в 1942 году, разрушены два верхних яруса колокольни.

Во время оккупации, при немцах в 1942 году церковь открыли. В 1949 году уцелевший ярус колокольни разобран. В 1950-х годах на основании разрушенной западной паперти возвели притвор, увенчанный главкой. В 1950 году в соборе произведён ремонт и восстановлены росписи. В 1988 году проведена реконструкция внутреннего убранства храма. В 1999 году восстановлена колокольня в её первоначальном виде. Реставрация собора в 2011-2018 годы на основе архивных материалов воссозданы в мельчайших деталях соборные росписи, кресты, 15 колоколов.