Церковь построена на казённый счет одновременно с тюремным замком в конце 1805 года.

Замок строился под руководством псковского губернского архитектора К. Жданова на основе одного из типовых проектов казённых зданий для губернских городов, разработанных архитектором А. В. Захаровым. По указу Псковской духовной консистории иконостас, ризница, утварь временно переданы из ветхой Успенской с Полонища церкви. Об окончании строительства тюремного замка Псковский губернатор Я. И. Ламбздорф 15 декабря 1805 года доложил министру внутренних дел графу В. П. Кочубею. В ответе министра 28 февраля 1806 года сообщалось указание Императора Александра I о том, чтобы «доставленные на время ... в устроенную при тюремном замке церковь церковные утвари и ризницу оставить в сей церкви для всегдашнего употребления без возврата», одновременно губернатору предписывалось рассмотреть вопрос о прибавке жалования священнослужителям этой церкви. Престол в церкви один. В 1873 году на средства Псковского вице-губернатора Урусова устроены две часовни: при входе в тюремный замок и в исправительном отделении. В 1870 году церковь расширена, в 1898 году вызолочен иконостас. Престол в церкви был один. Колокольни при церкви не было.

До 1870 года священники служили в тюремной церкви по найму. С 1900 года в церкви были штатный священник и вольнонаёмный псаломщик. В 1900 году в церкви служил священник Иоанн Антонович Городецкий, уроженец Порховского уезда, сын священника. С 1914 года священником служил Павел Матфеевич (Матвеевич) Жемчужин. Сведения о них после 1917 года не выявлены. Старостой церкви с 25 апреля 1903 года был псковский купец Николай Алексеевич Шелков. После 1917 года церковь закрыта. Церковное имущество «передано на хранение» в церковь Псковской Алексеевской общины Красного Креста. Здание тюремного замка использовалось и используется по прямому назначению и в наши дни, находится на улице Некрасова (до 1923 года Губернаторская).

В настоящее время в следственном изоляторе, который находится в бывшем тюремном замке, заключенными устроена церковь Святой Великомученицы Анастасии Узорешительницы. Освящена 2 ноября 2000 года. Первая литургия состоялась в 2001 г. в день памяти Святой Великомученицы Анастасии Узорешительницы.

 Адрес: ул. Некрасова, д. 39.