Деревянная кладбищенская церковь Рождества Богородицы к середине ХIХ века уже не могла удовлетворить верующих северо-западной части города Семенова. Прихожане задумались построить здесь большую каменную церковь. Инициатором возведения каменной кладбищенской церкви был благочинный протоирей Вознесенского собора Иоанн Иоаннович Райковский. Благодаря его ходатайству перед семеновской городской думой, под постройку храма была отведена дополнительная часть земли, прилегавшая к городскому кладбищу. Совместно с городской главой И.А. Бочкаревым 17 августа 1856 года составлен акт освидетельствования места под новую церковь.
В марте 1859 года епископ Антоний благословил построение церкви во имя Всех Святых. В 1863 году кирпичная кладка церкви была окончена, кроме небольшой части колокольни. Церковь возводилась по проекту, близкому к образцовым. Выстроена в русско-византийском стиле. Конструкция храма: одноглавый четверик, трапезной связанный с колокольней под луковичным куполом. В 1864 году проводились отделочные работы внутри храма. С мая 1864 года велось обустройство приделов в трапезной; правого во имя благоверного князя Александра Невского и левого в честь Святого Великомученика Георгия. Освящение правого придела проходило 3 октября 1866 года, а левого 9 июня 1867 года. В 1867 году была завершена кладка каменной колокольни. В 1875 году храм был украшен иконами, поставлен иконостас. В 1883 году церковь пострадала от пожара. Каменная ограда вокруг Всехсвятской церкви и кладбища была сооружена в 1904 году.
В 1930-х годах храм был закрыт, его венчания сломаны. Длительное время здание церкви использовали в качестве водокачки. В собственность Русской Православной церкви храм возвращен в начале 1990-х гг.
