В древности место, где стоит церковь, было краем обширного болота, называлось «усохой», «всосом». В 1371 году здесь впервые построена каменная церковь в честь Святителя Николая, впоследствии она сильно пострадала от пожара, в 1535 году разобрана. В 1536 году на её месте построена существующая каменная Николаевская церковь. В 1865 году пристроен придел Святого Апостола и Евангелиста Иоанна Богослова, освященный 3 (16) октября того же года архиепископом псковским и Порховским Феогностом. Престолов в церкви три. Главный престол - Святителя и Чудотворца Николая, северный придел - Сретения Господня, южный - Святого Иоанна Богослова. Сретенский придел предположительно построен одновременно с церковью. По указу Псковской духовной консистории от 31 августа 1786 года к ней приписаны церкви Святого Василия Великого на Горке и Святых праведных Богоотец Иоакима и Анны. Васильевская церковь была приписной до 1875 года, Иоакимо-Анненская - до 1897 года. В 1816 году приписана церковь Святого Великомученика Георгия со Взвоза. В юго-восточном углу церкви, вплотную к ней построена часовня «Неугасимая свеча». Здесь находился в чтимый псковичами и окрестными жителями образ Николая Чудотворца, перед которым постоянно горели свечи и лампады, отчего и получила свое название часовня. Дореволюционный историк А. Князев считал, что часовня древнее существующей церкви, которая и пристроена к часовне, а не часовня к ней. В иконостасе главного храма находились древние иконы, открытые после реставрации 1878 года. Их отмечал знаток древней иконописи обер-прокурор Синода К. П. Победоносцев.

Согласно легенде, когда в 1570 году царь Иоанн Грозный проезжал мимо церкви, как положено по уставу, зазвонил колокол, царский конь испугался, и царь велел отрубить «уши» большому колоколу. Одновременно с церковью на северной стене поставлена звонница. Позднее она перестроена в колокольню, на ней было семь колоколов. На полиелейном колоколе XYII века весом около 70 п. была следующая надпись: «Божиею милостию, Пречистыя Его Матери, Святыя Троицы помощию слит бысть колокол сей в городе Пскове к храму Николе Чудотворцу на Усоху лета 1619 майя 9 день на память иже во святых отца нашего Николы Чудотворца, при державе царствия благоверного христолюбивого Царя и Государя и Великого Князя Михаила Феодоровича всея России, и архиепископе Иоакиме Псковском и Изборском, и при священниках того храма Степане сыне Тетерине, да при старостах Мартине Силуянове и Андреи, а делали мастеры Савва да Кузьма, да племянник их Трофимко диачек. Аминь». Вес остальных колоколов неизвестен.

В приходе церкви были духовная семинария и частное женское учебное заведение Евдокии Костылевой.При церкви существовал хор из воспитанниц Псковского Ольгинского приюта.

Среди жертвователей на церковные нужды - староста церкви, псковский купец Иван Михайлович Кафельников.С 1906 года в церкви служил протоиерей Александр Семёнович Иеропольский, псаломщиком - Василий Петрович Панов. Сведения о них после 1917 года не выявлены.5 июня 1920 года отделом управления Псковского уездно-городского исполкома составлен акт передачи церкви религиозному обществу. 25 февраля 1929 года Псковский окрисполком принял постановление о расторжении договора с общиной церкви.В годы Великой Отечественной войны церковь сильно пострадала от артиллерийского обстрела и пожара. В 1946-1974 гг. Ю. П. Спегальским, В. А. Лебедевым и Б. С. Скобельцыным проведены реставрационные работы. Одним из итогов реставрационных работ явилось восстановление первоначальной звонницы и часовни.

В ноябре 2005 года церковь передана Псковской епархии. От внутреннего убранства в церкви ничего не осталось. Богослужения в ней начались одновременно с восстановительными работами. Архиепископ Псковский и Великолукский Евсевий подарил храму в качестве архиерейского благословения икону святителя Николая. В восстановлении храма помогли священники церквей Василия на Горке Андрей Большанин и Покрова Пресвятой Богородицы Андрей Вахрушев, архитекторы Владимир Никитин и Андрей Лебедев. Один из прихожан пришел в храм со своим инструментом и стёклами и, испросив благословения у батюшки, вставил стёкла во все рамы. Потом он же поправил крест на церкви, выполнил и другие работы. Когда Никольская церковь была построена, по своим размерам она уступала только Троицкому собору, в наши дни она на два метра скрыта культурным слоем, наросшим за века.

Адрес церкви: ул. Советская (Великолукская), д. 19.