В 1752 году в урочище реки Ишим была заложена небольшая крепость в честь святых первоверховных апостолов Петра и Павла. В центре крепости размещалась небольшая гарнизонная церковь. К 1850 г., когда крепости был присвоен статус города, в нем размещалось несколько тысяч жителей. При этом в городе размещались храмы: св. Петра и Павла, Покрова Божьей Матери, Вознесения Господня, св. Равноапостольной Марии Магдалины, св. Василия Великого.
В 1885 году перед градоначальником Петропавловска встал вопрос о необходимости открытия в городе нового кладбища. Старое кладбище, находившееся у собора Святого Вознесения, сильно разрослось и не могло вместить всех умирающих. На северной окраине города было выделено место для нового кладбища и намечено строительство при нем кладбищенской церкви в честь Всех Святых. Вот что пишет об этом журнал Омские Епархиальные Ведомости в разделе «Справки о храмах епархии» от 1900 г.: «Всехсвятская кладбищенская церковь, построенная в 1890-1894 гг. силами городских властей на средства Петропавловского купца Саввы Исидоровича Хлебникова и его супруги Анна Дмитриевны. Чудотворных и местночтимых икон нет».
По преданию, проект постройки храма благословил и внес деньги на его строительство подвижник благочестия ХХ столетия преподобный Иоанн Кронштадтский. Храм был построен в стиле корабля, на вершине которого, подобно мачтам, находятся 6 куполов. Колокольня-звонница встроена в храм и располагалась над входом в храм. Рядом со входом в храм помещены 2 иконы - пророка Божьего Илии и Крестителя Спасова Иоанна. В храме замечательный резной позолоченный иконостас.
Омские Епархиальные ведомости, давая сводку о состоянии приходов епархии, сообщали: «Всехсвятская кладбищенская церковь бесприходная. Капиталов и угодий, приносящих ей доход, не имеется. Земли при церкви нет. Для помещения причта на земле отведенной в вечное и бесспорное владение городской думой для церкви в количестве 3000 кв. сажен на средства господина Хлебникова выстроен одноэтажный, крытый железом дом». Из ведомостей расчета с церквями епархии Омского епархиального свечного завода видна финансовая жизнь храма. Так, за 1906–1907 годы, храм (являясь бесприходным) ходил в постоянных должниках. Расчетная ведомость от 31 декабря 1907 года сообщает под № 100 о долге Петропавловской Кладбищенской Всехсвятской церкви в размере 69 рублей 37 копеек.
При церкви была одноклассная, смешанная церковно-приходская школа, которая помещалась в доме, принадлежащем церкви. Школа содержалась на средства попечителя школы купца В. И. Черемисинова. Учительницей состояла имеющая диплом на звание домашней учительницы купеческая дочь девица Наталья Алексеевна Соколова. В школе обучались 37 мальчиков и 7 девочек. Из выписки из Журнала Омского Епархиального училищного совета от 17 марта 1908 г. за № 47: «Заявившим искреннюю любовь и преданность по школьному делу просить Его Преосвященство преподать благословение следующим лицам: учительнице Петропавловской Всехсвятской школы, священнической жене Евгении Лавровой архипастырское благословение и благодарность и объявить через напечатание в епархиальных ведомостях».
Храм представляет собой крестообразное в плане кирпичное сооружение сложной конфигурации. Построен в форме корабля, на вершине которого, подобно мачтам, находятся 6 куполов. Колокольня-звонница была встроена в храм и располагалась над входом (не сохранилась). Главный вход на территорию храма выполнен в виде трехарочных ворот из кирпича.
http://www.hvs.kz/istoriya-hrama-vseh-svyatyh-g-petropavlovska-chimkentskoy-eparhii