Первая деревянная кладбищенская церковь Всех Святых с колокольней в одной связке была построена на настоящем месте на средства купца Алексея Михайловича Гуляева в 1788 году.
В 1862 году эта церковь по ветхости была сломана, годный материал был употреблён на постройку сторожки. Проект на постройку каменной церкви был составлен в 1862 году. В 1863г. каменная кладбищенская церковь была построена надворным советником Павлом Андриановичем Кочневым по благословению епископа Вологодского и Великопермского Христофора. Церковь имела два придела: во имя Всех Святых, освящённый 23 мая 1864г., и в честь Воздвижения Креста Господня, освящённый 21 июня 1868 года. Крыша в церкви была деревянная, купола церкви и колокольни в одной связи с храмом были покрыты листовым железом.
В 1883 году для церкви были приобретены колокола, 1-й в 25 пудов и 2-й в 11пудов по 18 руб. 50 коп. за пуд, всего на 695 руб., сделаны ризы со стихарем, подризники белые и золотистые по две пары.
В 1889 году была достроена кладбищенская ограда, с каменным цоколем на лицевой стороне. Стоимость ограды составляла около 2000 руб.
Изъятие церковных ценностей происходило в 1922 году.
В 1940 - 1950 годах церковь использовалась под склад Райпотребсоюза.
После долгого перерыва, 14 ноября 1990 г. состоялось освещение церкви во имя Всех Святых и в ней вновь стали проходить службы.
Священники с 1990 г.
Первым священнослужителем, после большого перерыва, стал иерей отец Лукьян (сейчас он живет на Украине). С 1991 по 1999-й год приход возглавлял иеромонах отец Феодосий (Змушко). С 15 декабря 1999 по 14 марта 2004 года настоятелем церкви Всех Святых состоял иерей отец Вадим (Фидченко-Пухтий). С 14 марта 2004 года возглавляет церковь Всех Святых иерей отец Адам (Айдамиров).
В настоящее время при храме работает Воскресная школа (занятия проводятся для малышей дошкольного возраста), библиотека (православные церковные книги и журналы), видеотека (CD-DVD).