Шепелевское кладбище было устроено в середине XIX века на западной окраине Омска, за Бутырским форштадтом. Церковь была возведена напротив ворот кладбища в течение нескольких месяцев 1902 года. Средства на постройку храма были пожертвованы чиновничьей вдовой Бобровой и другими благотворителями. Средства собирались и благотворительными духовными концертами.
Церковь краснокирпичная, одноэтажная, в форме "корабля", зального типа с восьмигранным барабаном под низким куполом с луковичной главкой и изящной шатровой колокольней. Стены храма прорезаны арочными окнами, фланкируемы лопатками и оформленными нишами по краям от южного входа. Каждая грань деревянного барабана имеет килевидное завершение. Перед западным входом был пристроен деревянный тамбур. Стены гладкие с пилястрами, сложный карниз. Окна полуциркульные оформлены наличниками. Колокольня: ярус звона восьмигранный с арочными проемами. До революции храм не имел своего причта, был приписан к Омскому Успенскому собору.
В 1920-е годы община была "тихоновской" ориентации. С 1926 по 1928 годы приход храма составлял от 150 до 201 прихожанина.
Храм закрыли в начале 1930-х годов и в 1940-е годы снесли. Сейчас на месте кладбища и храма построены корпуса завода.
Наталья Лебедева "Церковь во имя Святого Павла Комельского Чудотворца в г. Омске" // Сайт "Памятники культового зодчества Омского Прииртышья". http://newasp.omskreg.ru/hramy/Omsk/pavla.htm