Казачье кладбище возникло во второй трети ХIХ века к востоку от Казачьего форштадта, на его территории были выделены участки для захоронений кадетского корпуса, католического и холерного кладбищ. Во время Великой Отечественной войны на нем хоронили воинов, умерших в омских госпиталях. Кладбище находилось в конце Никольского проспекта (ул. Красных Зорь) за Шкроевской улицей (совр. ул. Куйбышева).
Первоначально на нем была построена часовня. А в 1859 г. на средства омского Городского головы — купца, коммерции советника, почетного гражданина Владимира Петровича Кузнецова в центре кладбища возвели каменную церковь. В труде о сибирской иконописи протоиерея о. Александра Сулоцкого сказано, что иконы для иконостаса Кладбищенской церкви, а также для храмов в Каркарале и Кульдже, В.П. Кузнецов заказывал в Москве. Интерьер храма славился прекрасным хрустальным паникадилом, пожертвованным В.П. Кузнецовым. В.П. Кузнецов, исполняя должность Городского головы, построил по проекту Э.И. Эзета новый Ильинский мост через Омь. Умер он 29 марта 1870 г. Генерал-губернатор Западной Сибири А.П. Хрущов просил разрешения у архиепископа Сибирского и Тобольского похоронить В.П. Кузнецова в Кладбищенской церкви, но архиепископ Варлаам ответил, что это запрещено законодательством.
Церковь не сохранилась, но ее уникальные фотографии дают возможность определить его стилистику как официальное направление в «русском стиле». Храм был построен из красного кирпича, оштукатурен и побелен, имел трехчастную композицию. Одноглавая церковь была оформлена классическими пилястрами и антаблементом. Барабан купола и обрамление оконных проемов выполнены в виде килевидных арок. Восьмигранная колокольня была шатровая с одним ярусом звона. Возможно, автором проекта Всехсвятской церкви является архитектор хозяйственного правления Сибирского казачьего войска Гавриил Степанович Вершинин. Притвор и колокольню пристроили в 1896 г. на средства омского купца Григория Васильевича Шкроева, что позволило присутствовать на службе 400 человекам.
В храмовый праздник совершался крестный ход по кладбищу. При церкви была часовня-памятник. В кладбищенской Всехсвятской богадельне в 1914 г. проживало семь женщин. Настоятелями храма были выдающиеся омские проповедники: в 1900-е гг. протоирей Василий Пляскин, в 1910-е гг. благочинный омских городских церквей градо-Омский противосектантский миссионер протоиерей Михаил Орлов.
Во время Первой мировой войны умерших воинов и беженцев отпевали бесплатно. Вблизи храма были похоронены известные граждане Омска: военный губернатор Акмолинской области генерал-лейтенант В.С. Цытович, протоиерей и историк Церкви А.И. Сулоцкий, архитектор И.Г. Хворинов, купцы В.П. Кузнецов, Г.В. Шкроев, С.С. и Ф.С. Волковы, С.Н. Москалитин, О.В. и В.Т. Разумовские, позднее, доктор Ф.И. Билль, ученый П.Л. Драверт, профессор ОмГМИ Н.Д. Либеров…
С 1920 г. храм был приходским. Приход общины был одним из самых больших в Омске: по данным за 1926 год – 89 человек, 1927 – 312. В 1937 – 1938 гг. прихожан было 30 человек, в храме служили священники Киселев и Татищев, председателем общины была А.М. Суковатицина. Закрытие церкви произошло в феврале 1938 года. В храме разместили склад «Водник».
Во время Великой отечественной войны на многочисленные ходатайства верующих об открытии Всехсвятской церкви в Омске следовали отказы со ссылкой, что она находится в километре от действующего храма, что является заведомой ложью, так как действовавшая Крестовоздвиженская церковь находится на другом берегу Оми, за много километров от Казачьего кладбища.
Судьба Всехсвятской церкви на Казачьем кладбище волновала сотрудника, а затем директора краеведческого музея А.Ф. Палашенкова. В 1948 г. он пытался открыть в здании храма музей истории города Омска. В ходатайстве от 10 апреля 1949 г. Андрей Федорович указывал на то, что омский музей располагает большим собранием планов, чертежей, фотографий и вещей, которые было негде экспонировать. Городской совет принял решение о передаче храма для размещения музея и направил запрос в Совет министров СССР. Но начинание Андрея Федоровича не увенчалось успехом. Совет по делам Русской Православной Церкви при Совете Министров СССР 9 мая 1949 г. принял постановление: «Считать несвоевременным использование кладбищенской церкви под музей». Последние годы своего существования церковь пустовала и постепенно разрушалась.
31 января 1966 г. состоялась первая учредительная конференция областного отделения Всероссийского добровольного общества охраны памятников истории и культуры, внесшего значительный вклад в спасение местных памятников культового зодчества. Но и в этот период не обошлось без потерь, так в 1975 году была снесена Всехсвятская церковь на Казачьем кладбище. На территории Казачьего кладбища построили детскую и инфекционную больницы.
В конце 2004 года по инициативе губернатора Омской области Л.К.Полежаева выстроен новый деревянный храм во имя Всех Святых на этом историческом месте. Митрополит Омский и Тарский Феодосий освятил храм и отслужил первую литургию 7 января 2005 года, в день Рождества Христова.
http://vsehsvyatskiy.prihod.ru/o-xrame/