Каменная церковь Царя Константина и Матери его Елены, построена предположительно в первой трети XVI века и возможно являлась монастырским храмом. На основании обнаруженных на сегодняшний день архивных материалов, к сожалению, можно констатировать тот факт, что псковские летописи не упоминают ни даты строительства, ни перестроек храма Константина и Елены. Первое, наиболее раннее датированное упоминание церкви «Царя Константина изо Пскова с Песку…» находим в Писцовых книгах к. XVI в., а первое описание – в «Офицерских описях» 1763 года. Изначально в церкви Константина и Елены не было полноценного придела, клиросная палата использовалась как ризница или книгохранилище, а придел священномученика Власия расположился в дьяконнике. Очень сильно храм пострадал в начале XVII века при, а монастырь был сожжен и прекратил существование. С большой долей уверенности можно говорить о том, что бедствия Ливонской войны, Смутного времени и нашествие на Псков войск шведского короля Густава – Адольфа в 1615 году не могли не сказаться на благосостоянии храма. Четырехскатное покрытие взамен восьмискатного могло появиться в XVII в. после восстановления. На основании одной надписи на храмовой иконе Окулич-Казарин предложил 1681 год как дату перестройки храма.
Можно только предполагать, что к отдельному строительному этапу (не позднее сер. – II пол. XVIII ст.) может относиться возведение южного теплого придела Святого Власия взамен упраздненного малого придела в диаконнике. Н.Ф. Окулич-Казарин называет его новым, сооруженным неким Урвиным. Главный храм оставался холодным, по крайней мере до 1890-го года, когда впервые упоминается печь в приделе. К последней четв. XVIII в. – помимо придела, может быть отнесена надвратная колокольня и каменная ограда погоста. На колокольне висели шесть колоколов, два из них – времен царя Ивана Грозного.
В 1808 году церковь предназначалась к сносу как совершенно ветхая, однако Святейший Синод снос церкви не разрешил. В 1814 году церковь Константина и Елены по бедности была приписана к Димитриевской кладбищенской. В апреле 1836 года она была приписана к церкви Святого Апостола и Евангелиста Иоанна Богослова на Мишариной горке. В XIX веке в престольный праздник около храма устраивалась ярмарка.
5 мая 1936 года Псковский окрисполком принял решение о закрытии церкви. Дальнейшая судьба колоколов не известна. Здание храма использовалась как архивный склад, зернохранилище, склад музея, мастерские для художников, клуб спелеологов.
В годы Великой Отечественной войны церковь получила частичные повреждения кровли, стен, наружной и внутренней отделки. Решением Псковского горисполкома от 8 июня 1948 года закрыто для захоронений кладбище вокруг церкви. В семидесятых годах пожар уничтожил крышу колокольни, реставрационными мастерскими была возведена временная крыша.
В 1988 году организована община верующих, которая обратилась к властям о возвращении храма Церкви. 04 января 1989 года состоялось первое Богослужение. Решением Псковского горисполкома от 14 марта 1990 года церковь официально возвращена верующим, началось её восстановление. Первым настоятелем храма был иерей Владимир Рубчихин. 20 ноября 1991 года указом правящего архиерея, архиепископа Псковского и Порховского Владимира (Котлярова), настоятелем храма был назначен священник Пантелеимон (Ледин).
За прошедшие годы церковь и колокольня приведены в порядок, храм обнесён каменной оградой с угловыми башнями, в 1997 году возведена часовня Блаженной Ксении Петербургской. Сейчас на колокольне 8 колоколов работы Воронежских мастеров фирмы «Вера», пожертвованных прихожанами. На территории так же возведены трапезная и сторожка. В 1999 году началась, а осенью 2010 завершилась роспись храма фресками. Храм расписан прихожанином храма художником-реставратором Александром Миловановым. Все работы по благоукрашению и реставрации проведены прихожанами и добровольными помощниками.
В 2006 году иконостас и иконы храма были украшены басмой трудами Елизарова Анатолия Николаевича.
В 2016 году завершился полный ремонт храма и устроена изразцовая печь в приделе священномученика Власия.
Настоятель храма: схиигумен Пантелеимон (Ледин)
Группа ВКонтакте: https://vk.com/club204172446
