«Кладбищенская Всехсвятская церковь бесприходная, однопрестольная, в честь всех святых. Построена в 1890 – 1894 годах усердием петропавловского купца Саввы Исидоровича Хлебникова и жены его Анны Дмитриевны. Здание церкви и связанной с ней колокольни каменные, обнесены железной на каменном фундаменте оградой. Особо чтимых икон и земли при церкви нет» / Из книги Голобушина И. Справочная книга Омской епархии. Омск, 1914. Храмы и приходы Петропавловска Акмолинской области / .-С.95
Задумывалась она как кладбищенская, сотни горожан нашли близ нее вечное упокоение. Среди известных – Григорий Иванович Казанцев – почетный гражданин города Петропавловска, умер в возрасте 71 года 20 июля 1913 года.
«Омские епархальные ведомости» вековой давности свидетельствуют: строительство церкви происходило с благославения святого праведного Иоанна Кронштадского, бывшего проездом в Петропавловске. Паствы своей праведник не забывал, в дальнейшем делал крупные взносы на строительство. Велось оно за счет пожертвований купечества, среди которых особенно постарались для общества купцы Хлебниковы – на их средства в 1898 году была открыта и церковноприходская школа. Учили здесь толково и всерьез. Государство тратило на школу 300 рублей в год. В 1900 году при церкви открывается богадельня, через 7 лет по указу Святого Синода – женская община – монастырь, первой настоятельницей которого стала монахиня Виталия.
Иконостас в церкви сегодня тот же, что и век назад. Среди реликвий есть редчайшие: привезенный безвестным прихожанином из Святой земли медальон с частицами мощей архидиакон Стефана; в одной из икон находится частица мощей Пелагеи, тоже прославившейся на заре христианства. Бережно хранится подаренная храму Николаем II икона, на которой изображены трое покровителей семьи Романовых – св. Николай, мученица Александра, св. Алексей, митрополит Московский
В стенах Всехсвятской церкви совершал службу епископ Петропавловский, викарий Омский Мефодий, казненный в 1921 году во время крестьянского восстания. Место захоронения епископа неизвестно, так как власти опасались народного почитания. Его останки нашли себе место упокоения в одной из братских могил того времени. Владыка Мефодий причислен к лику новомучеников Российских в 2000 году во время Поместного собора Русской Православной Церкви. Всехсвятская церковь – единственная – ни на один день не закрывающая дверь для людей: из семи храмов в Петропавловске пять были разрушены, а Собор св. Петра и Павла был возвращен общине верующих лишь в середине 40-х годов.
Земли, находящиеся во владении церкви и здания, были конфискованы. Кладбище вокруг церкви разрушено, на его месте сейчас находится парк и построен стадион «Авангард» ныне стадион «Карасай».
В настоящее время настоятель храма – иерей Виктор (Михейкин), рукоположен в 1992 году епископом Елевферием в г. Чимкенте. С 1999 года при храме действует паломническая служба. Трудами отца Виктора действует воскресная школа. Несомненным успехом в церкви считают организацию «Православногобратства», рассматриваемого как прообраз будущего моностыря. Подгруппа братства «Русский паломник» вот уже несколько лет отправляется по святым местам.
Ныне церкви вернули кладбищенскую территорию.