В 1888 году на территории верхотурской тюрьмы была построена церковь в честь иконы Пресвятой Богородицы «Всех скорбящих радость». Возводилась она на пожертвования горожан, сбором которых занимался исправник Г.П. Межецкий. Церковь была каменной, одноэтажной и примыкала к стене тюремного замка, отдельно от неё построили деревянную часовню. Освящение новой церкви прошло 19 мая 1892 года, приписана она была к Троицкому собору. В 1897 году её стены на средства благотворителей были украшены фресками. На содержание церкви земство выделяло 93 рубля 80 коп. в год, на отопление четырёх печей расходовалось 32 сажени дров, на освещение 13 пудов керосина, сторож и надзиратель получали 420 рублей в год. Кроме этого, выделялись средства на приобретение для арестованных религиозной литературы. В городе существовало попечительство о тюрьмах, во главе которого стоял купец Николай Иванович Мухлынин. В состав попечительства входили: архимандрит Иов, протоиерей Александр Александрович Удинцев, городской судья Николай Осипович Высоцкий, коллежский советник Василий Гордеевич Пастухов, уездный врач Александр Францевич Семашко, купцы Михаил Филиппович Путимцев и Виктор Яковлевич Бурдаков. Смотрителем тюремного замка был Николай Васильевич Конюхов, фельдшером – Александр Иванович Катычев. Храм был закрыт в 1919 г.