Построена в 1907 г. К строительству были привлечены опытные каменщики из алтайского села Жуланиха под руководством мастера Рогова. Рядом с церковью отстроили просторный дом для священника и отвели место для погоста, оградив все железной оградой. Тут же, в небольшом сквере на пьедестале, 19 февраля 1894 г. установили бронзовый памятник царю-освободителю Александру II. Освятил храм 8 апреля 1907 г. по благословению епископа Томской епархии настоятель прихода протоиерей Леонтий Попов, окончивший Тоб. ДС. С 15 июля 1861 г. он являлся духовником окружных церквей. Прослужив более 40 лет, умер в 1910 г. и погребен у алтаря построенного при нем каменного храма.
Фасады храма выполнены в стиле эклектики. В плане он напоминает Троицкую церковь в селе Красное, тем более, что строились они в одно время в начале XX века. Состав прихода на 1914 г.: с. Салаирский рудник; д. Гавриловка; заселки Кулаевский и Осиновский. Состав причта: священник, диакон и псаломщик. Прихожан 3184 чел. Земли при ней числилось 101 десятин. Благочиние 13 Кузнецкого округа. В приходе имелись приписная кладбищенская церковь (Покрова Пресвятой Богородицы) в с. Салаирский рудник с 1861 г.; молитвенный дом Успения Пресвятой Богородицы в д. Гавриловке с 1872 г. на средства урядника Д.П. Ковцова; церковно-приходская школа в д. Гавриловке с 1898 г.; двухклассное училище гражданского ведомства в с. Салаирский рудник с 1902 г. с 200 учениками; церковная библиотека с фондом 287 экз.
В советское время в 1933 г. Петропавловская церковь была разорена, колокола и кресты отправлены на переплавку, памятник Александру II исчез, а само здание церкви пришло в запустение. В 1936-37 гг. репрессировали оставшихся священников: отцов Павла, Якова, Симеона и старосту Тимофея Кротова. В 1941 г. поселок Салаир преобразован в город.
Еще в 1970-х гг. в связи с приближением выработок Салаирского рудника местные власти намеревались полностью уничтожить храм, начав вблизи взрывные работы, чем нанесли серьезный урон фундаменту. Были сняты кресты с куполов, разрушены привратные каменные колонны. Был даже сочинен официальный документ с авторитетными подписями «специалистов», по которому храм объявлялся не представляющим архитектурно-исторической ценности. Благодаря представителям Общества охраны памятников истории и культуры, краеведам и особенно директору Салаирского рудника А.М. Руденко, удалось восстановить истинную значимость храма как памятника историко-культурного наследия русских сибиряков. После передачи Советом Министров РСФСР храма Русской Православной Церкви с 1989 г. стараниями настоятеля прихода священника Сергия Мосолова ведутся активные реставрационные работы по проекту архитекторов города Новокузнецка.
24 августа 1991 г. епископ Красноярский и Енисейский Антоний освятил восстанавливаемый храм, а к 1995 г. все работы уже были закончены. По пятницам, субботам и воскресеньям, а также в двунадесятые праздники проводятся богослужения, а на престольный праздник 12 июля и в день памяти мчч. Кирика и Улиты 28 июля ежегодно устраиваются крестные ходы к сооруженной в 1995 г. деревянной часовне у чудотворного родника. На погосте у храмового алтаря восстановлена могила протоиерея Леонтия Попова. В храме имеются две старинные иконы: Божией Матери «Тихвинская», освященная в 1908 г. на Афонской Горе в Русском Андреевском Общежительном ските; икона вмч. и целителя Пантелеимона.