Церковь во имя Всех Святых (Всехсвятская) была построена в центре Казачьего кладбища в 1859 г. на средства потомственного почетного гражданина известного купца и городского головы В. П. Кузнецова. В 1896 г. к ней пристроили колокольню на деньги омского купца Г. В. Шкроева. Церковь вмещала в себя до 400 человек. Храм был квадратным, четырехскатную крышу  венчала луковичная главка на высоком восьмигранном барабане. Арочные окна обрамляли килевидные наличники, а фризовый пояс украшал ряд сухариков. Грани колокольни имели арочную форму с покрытием в виде килевидных бочек. Завершалась колокольня шатром с окошечками на всех гранях и луковичной главкой. В феврале 1939 г. церковь закрыли. В ней разместился склад «Водник». Верующие неоднократно ходатайствовали об открытии храма в послевоенный период. В 1948 г. директор краеведческого музея А. Ф. Палашенков пытался открыть в здании храма музей истории города Омска.  Однако Совет по делам русской православной церкви при Совете Министров СССР 9 мая 1949 г. принял постановление: «Считать несвоевременным использование кладбищенской церкви под музей».  Последние годы своего существования церковь пустовала и постепенно разрушалась. В 1975 г. она была снесена, а в 2005 г. восстановлена.

Лит.: Бродский И. Е. Казачье кладбище // Омский некрополь. – Омск, 2005. – 22-24; Лебедева Н. И. Всехсвятская церковь на Казачьем кладбище // Храмы и молитвенные дома Омского Прииртышья / Н. И. Лебедева. – Омск, 2003. – С. 26, 104, 153: ил.; Соколенко Ю. Кладбищу вернули храм // Труд. – 2005. – 13 янв. – С. 1.