В октябре 1822 года Пермский гражданский губернатор Кирилл Яковлевич Тюфяев обратился в Министерство Внутренних Дел за разрешением надстроить второй этаж над арестантской казармой тюремного замка в городе Перми, так как старое здание не вмещало всех арестантов, число которых год от года увеличивалось. Губернатор предполагал устроить на втором этаже не только помещения для арестантов, но и лазарет, а также церковь, чтобы "заключающиеся в губернском тюремном замке узники в продолжение содержания не могли быть лишены духовного благочестия и нравственного назидания, только для них необходимого". Вместе с докладом в министерство были доставлены план и смета предполагаемых построек, составленные губернским архитектором Васильевым.

Пермская губернская тюрьма. [Нач. XX в.] ГАПО.Ф/ф.Ист.№329.

Получив разрешение МВД и Святейшего Синода, губернские власти приступили к реконструкции тюремного замка. Устройство тюремной церкви проходило при активном участии пермского общества: многие видные чиновники и заводчики пожертвовали на ее строительство и содержание несколько тысяч рублей, заводчик Ярцев закупил в Москве две пары риз и утварь для престола и жертвенника, на Суксунском заводе отлили для тюремной церкви три медных колокола.

В 1829 году строительство было закончено. Епископ Пермский и Екатеринбургский Мелетий освятил тюремную церковь во имя Божьей Матери "Всех скорбящих радость". К церкви был определен постоянный штат - священник и два причетника, жалованье им выплачивал Пермский тюремный комитет. В 1878 году при реконструкции тюремного замка церковь была перестроена при активном участии церковного старосты, почетного потомственного гражданина Петра Георгиевича Шавкунова.

Церковь при губернской тюрьме существовала до 1918 года. Декретом СНК "Об отделении церкви от государства и школы от церкви" было запрещено совершать религиозные обряды и церемонии в государственных и иных публично-правовых общественных помещениях, а также размещать в них какие-либо религиозные изображения. В мае 1918 года настоятель Богородице-Скорбященской церкви протоиерей Андрей Знаменский получил уведомление из Пермской губернской тюремной инспекции о том, что по распоряжению Юридического отдела исполнительного окружного комитета от 2 мая с. г. "все духовные лица, находящиеся на службе в тюремном ведомстве, увольняются от своих должностей". Штат тюремной церкви был упразднен, выдача жалованья прекращена, хотя у священника оставалось право продолжать богослужения за вознаграждение по соглашению с тюремным ведомством, при условии содержания церкви на собственные ее средства.

В советское время тюрьма в Разгуляе и церковь при ней капитально перестраивались. В настоящее время в здании бывшей губернской тюрьмы размещен следственный изолятор.

В 1871 году за городской заставой на Сибирском тракте был окончательно устроен пересыльный замок для арестантов, следующих через Пермь в Сибирь. 13 августа 1872 года при пересыльном замке состоялась закладка храма во имя святого Николая Чудотворца. Церемонию закладки первого камня и водружения креста совершил сам архиепископ Антоний.

Ф.К. Каменский и Г.К. Каменский, пермские предприниматели и благотворители. ГАПО.Ф.печ.изд.№302.С.173.

Мысль основать эту церковь принадлежала Пермскому губернатору Н.Е. Андреевскому, а содержался храм всецело на средства известных предпринимателей и благотворителей братьев Федора Кузьмича и Григория Кузьмича Каменских. За год с небольшим церковь при пересыльной тюрьме была построена и освящена 18 ноября 1873 года во имя Николая Мирликийского Чудотворца.

Каменное здание церкви помещалось рядом с корпусом для арестантов исправительного отделения, которые проходили на богослужение через особый вход, ведущий на церковные хоры. Колокольни при церкви не было, но возле алтаря находилась звонница с пятью небольшими колоколами. Церковный причт (священник и псаломщик) получал жалование от тюремного ведомства. Последние документы о деятельности Николаевской тюремной церкви относятся к сентябрю 1918 года.

В настоящее время в капитально перестроенном здании пересыльной тюрьмы размещается кукольный театр.