Первое упоминание о церкви относится к 1466 году, когда она в один день построена по обету для избавления Пскова от мора (эпидемии). Каменная церковь построена в 1495 году. В древности рядом находились Варлаамские ворота, через которые 13 сентября 1472 года в Псков въехала Софья Палеолог, невеста Великого князя Ивана III Васильевича. В 1615 году здесь был центр обороны города от войск шведского короля Густава Адольфа, именно здесь шведы 9 октября пошли на решительный штурм, но город выстоял. Во время одного из штурмов главный удар шведов был нацелен на Варлаамовскую башню, псковичи взорвали её вместе с засевшими там врагами. Шведы также были поражены «богоранными стрелами» от сильной пальбы с купола церкви. В ризнице Варлаамовской церкви хранилась «Повесть о прихождении Свейского короля Густава Адольфа ко граду Пскову», написанная сразу после исторических событий. В память о тех событиях до 1917 года вокруг города проводились крестные ходы, в Варлаамовской церкви совершалась заупокойная лития по православным воинам.

 В 1788 году к ней приписана церковь Воскресения Христова со Стадища. В 1808 году церковь предназначалась к сносу как совершенно ветхая, однако Святейший Синод снос церкви не разрешил. В 1831 году на западной стене церкви устроены хоры, на которые вела чугунная винтовая лестница, сделанная в 1892 году. Теснота и сырость придела вызвали его перестройку, расширение и удлинение в 1858 году. Освящен придел в 1861 году. В 1900 году перестроены западная и средняя части придела вместе с папертью. Престолов в церкви было два, главный престол - во имя Святого Преподобного Варлаама Хутынского, в приделе - во имя Святителя Николая Чудотворца.

На западной стороне церкви поставлена звонница на трех каменных столбах, на ней висели шесть колоколов: два больших, два средних и два подзвонка. Большой колокол весил 67,5 п., отлит в 1870 году валдайским мастером Стуколкиным. На втором большом колоколе была надпись: «Зри зачала на меньшем колоколе при митрополите Данииле и при наместниках Псковских при князе Феодоре Васильевиче Лопате и при великом князе дьяке Мисюре Мунехине повелением Великого князя воеводы Ивана Артемиевича Широноса городщика и повелением раб Божиих старосте Терентия Мокроуса и Моисея Рошете и всех сусед романских, а мастеры Андреевы дети Михаил священник бывший да Максим диак. Слава Свершителю Богу».

 В 1895 году открыто церковно-приходское попечительство. В приходе находился епархиальный свечной завод, при котором в 1898 году открыта богадельня для престарелых женщин духовного звания. В 1900 году их было 13 человек. Священник Андрей Николаевич Розов, служивший в 1835-1848 годах, в собственном доме содержал приходскую школу. В 1899 году открыты две церковно-приходские школы, мужская и женская. Для школ старанием и на средства церковного старосты - купца Василия Яковлевича Сафьянщикова - построено новое каменное двухэтажное здание. У Варлаамовских ворот в 1871 году вместо деревянной часовни построена каменная часовня, молебны в ней совершались на праздник Рождества Богородицы. 26 августа 1916 года священником в Варлаамовскую церковь назначен кандидат богословия Московской духовной академии Николай Цветаев. Сведений о нём после 1917 года не выявлено.

21 июля 1920 года отделом управления Псковского уездно-городского исполкома составлен акт о передаче религиозному обществу Варлаамовской и приписанной к ней Воскресенской церквей. Постановлением Псковского горисполкома от 9 июня 1935 года закрыта часовня Рождества Богородицы.28 ноября 1938 года президиум исполкома Ленинградской области, в состав которой в 1927 году вошла бывшая Псковская губерния, принял решение о закрытии церкви. Решением Псковского городского совета от 11 сентября 1939 года в церкви разрешено открыть кинотеатр.В 1942 году при церкви Василий Васильевич Миротворцев организовал кружок молодёжи, где читалось Евангелие, велись беседы на религиозные темы. В ходе боевых действий церковь получила частичные повреждения кровли, стен, наружной и внутренней отделки.Церковь действующая, 25 августа 2006 года архиепископ Псковский и Великолукский Евсевий совершил чин освящения семи колоколов. Среди жертвователей -благодетели, прихожане, в основном многодетные семьи. Внёс свою лепту в литье колоколов и правящий архиерей. Каждый колокол назван по имени Царственных мучеников: Государь НиколайII, Государыня Александра Федоровна, Цесаревич Алексей, великие княжны Мария, Ольга, Татьяна, Анастасия. Жертвователи на Мариинский колокол посвятили его также преставившемуся младенцу Марии. На большом колоколе отлита икона Царской семьи. В наборе есть и восьмой колокол - для гармонизации. Отливали колокола по старинной технологии в городе Тутаеве Ярославской области. Общий вес колоколов 900 килограммов.

Адрес церкви: улица Поземского (бывшая Нарвская),д. 53.