В начале XX в. на территории современного города Анжеро-Судженск существовало 2 деревянные церкви.
Первая, построенная в 1903 г. и относившаяся к Благочинию ж/д церквей прп. Макария Египетского с одним куполом и колокольней, находилась на Анжерских каменноугольных копях в районе современного городского сада. Рядом с храмом располагался погост, в отдалении был пруд и колодец со святой водой, куда на праздник Крещения совершали крестный ход. В приходе имелись одноклассная школа ж/д ведомства и церковная библиотека. В 1929 г. здание храма было разрушено.
Вторая церковь Святой Троицы находилась в поселке при Судженских каменноугольных копях с 1907 г. При храме имелись училище гражданского ведомства и церковная библиотека. В 1913-15 гг. настоятелем Троицкого храма служил священник о. Василий Мамаев.
В 1924 г. решением бюро райкома партии церковь была закрыта, а здание вначале было передано под пионерский клуб. В послевоенные годы под новую церковь Покрова Пресвятой Богородицы приспособили небольшой частный дом по ул. Бийской 85, оборудовав в нем алтарь. На колокольне были установлены один большой и три малых колокола. Со склада Берикульской МТС, оборудованной в бывшем здании Покровской церкви с. Белогородка Мариинского района, с разрешения властей были взяты иконостас, иконы, хоругви, церковная утварь.
В 1948 г. в центре города по ул. Дорожной с разрешения властей настоятелем прихода иеромонахом Петром Сеньковым началось строительство нового деревянного храма, возведенного к январю 1949 г. Однако местные власти распорядились разобрать еще не освященный храм и перенести на окраину в болотистое место. Отца Петра отстранили от служения, а церковный староста Кондрат, собиравший деньги на строительство, был осужден на несколько лет заключения. Новым настоятелем был назначен протоиерей Александр Сычугов, при котором здание было перенесено на нынешнее место с переосвящением престола в честь первоверх. апп. Петра и Павла архиепископом Новосибирским Павлом в 1953 г.
В 1985 г. настоятелем храма назначается священник Николай Гомзяк. К 1000-летию крещения Руси настоятель о. Николай произвел реконструкцию храма. Были сооружены купол, колокольня, металлическая ограда, подсобные помещения. Храм сразу же преобразился.
В 1995 г. завершено сооружение каменного крестильного храма свт. Иоанна Тобольского. В нем изготовлен и установлен богатый иконостас, сделаны росписи стен.
В 1994 г. открыта воскресная школа, имеется библиотека с фондом 2 тыс. экз.
В 1999 г. закончена роспись основного и крестильного храмов. Св. престол основного храма назван в честь Петра и Павла; крестильный храм - в честь свят. Иоанна Тобольского.
Источник: Петро-Павловский храмовый комплекс
