Храм заложен в 1813 г. на кладбище за Херсонскими воротами по прошению купца 2-й гильдии С.А. Александрова и построен на его деньги в 1819 году. Освящен храм был только в 1836 г. Был заложен в честь св. Екатерины, но, видно, после смерти  купца Александрова по неизвестным нам причинам был именован в честь Всех Святых.

В 1844-45 г.г. курский архитектор начертил план и фасад церкви, которые  показывали, что церковь представляла собой кирпичный одноглавый храм в  классическом стиле: круглый в плане центральный объём, круглый барабан с купольным сводом, трёхъярусная колокольня и притвор.

 В 1899 г. епархиальным архитектором Слесарёвым была выполнена пристройка северного придела, осуществлённая в начале XIX века. Им же была разработана и южная  пристройка, но она не была осуществлена. В северном приделе был устроен престол св. великомученицы Екатерины.

В 1939 г. храм был закрыт. Но осенью 1941.г. он вновь открылся.

В 1992 г. по благословению архиепископа Курского и Белгородского Иувеналия при настоятеле Александре Рогозинском по проекту архитекторов Н.Л. Брагина и Д. А. Кубрина была осуществлена пристройка южного придела, освященного в честь прп. Алексея, человека Божия. На прежнем месте была восстановлена колокольня. Рядом с церковью был построен церковный дом. Архитектурный комплекс был обнесён оградой. Решением Курского облисполкома от 16.02.1989 г. церковь отнесена к памятникам архитектуры местного значения.