Церковь построена из плиты в 1413 году на месте более древней церкви 1377 года, вблизи крепостной стены Среднего города (стена не сохранилась). Церковь Василия Великого -единственная сохранившаяся в Пскове церковь начала XY века, времени расцвета Псковского вече. Её строительство связано с именем знатного «Немчина» Василя Дола, который считался предком псковских дворян Яхонтовых. Есть предположение, что в XYI веке церковь  была разобрана и отстроена заново, но документального подтверждения этой версии нет. По указу Псковской духовной консистории от 31 августа 1786 года стала приписной к церкви Святого Николая со Усохи. В 1821 году архитектор Ябс и протоиерей Лебедев отмечали, что в церкви ветхая кровля, в стенах и сводах трещины, прихода в церкви нет. В связи с отсутствием средств для ремонта церковь предназначалась к сносу, однако Святейший Синод «во уважение ходатайства жителей города Пскова» повелел церковь не сносить. Однако средств на её ремонт по-прежнему не было, и во время визита в Псков Императора Николая  она была прикрыта забором. В 1875 году по ходатайству настоятеля Крыпецкого монастыря игумена Николая церковь стала подворьем монастыря. Ежегодно 29 августа (11 сентября) сюда крестным ходом приносили монастырские иконы, которые оставались здесь до 7 (20) сентября. В церкви в эти дни совершались торжественные богослужения. С 1875 по 1879 год богослужения в церкви совершались ежедневно, часть братии Крыпецкого монастыря постоянно находилась при церкви. В 1879 году указом Псковской духовной консистории богослужения в церкви по малочисленности братии прекращены, братия возвращена в монастырь, с этого времени богослужения в ней совершались только во время принесения икон крестным ходом. Придел слева, по документам XIX века и на 1914 год, был посвящен Святому Алексию Человеку Божию.

Звонница находилась на крепостной башне Среднего города. Некогда на звоннице Васильевской церкви висел осадный колокол, в который звонили в 1581 году при виде шедшего на приступ войска Батория. Колокольня построена в связи с церковью после 1740 года. Во второй половине XIX века на ней висели четыре древних колокола, вес первого - 20 п., второго - 15 п., третьего - 5 п. Вес четвёртого колокола неизвестен. В 1914 году добавлены два подзвонка. Надпись на одном колоколе гласила: «Лета 7041 (1533) месяца сентября в 8 день на Рождество Пречистой Богородицы Божиею милостию слит [были] сии колоколы к храму святого великого Василия в Старый город на горку при великом князе Василии Ивановиче всея Руси и при архиепископе велика Новагорода и Пскова владыке Макарьи во область Святыя Живоначальныя троицы в великом богоспасаемом и преименитом и славном граде Пскове повелением раб Божиих старост Алексея Федотьева сына Буиноса, зри конец летописца». На меньшем колоколе надпись была следующая: «Зри начало летописца на большом колоколе да Микуле Остафьева сына Колпачникова городов ... воеводы Дмитрия Александрова сына Кубаса Сарыхозина, да и гостей веденных и всех сусед святаго великаго Василия Федорова сына да при Петре Феодорова же сына а мастер лил Андреев сын Максим псковитин многогрешный и грубый смыслом. Слава Свершителю Богу». Весил этот колокол около 15 пудов.При церкви не было часовен. Не было также библиотеки и ризницы, всё нужное для богослужения приносилось из монастыря во время крестного хода. При церкви находилось монастырское подворье: каменный двухэтажный дом с двумя флигелями и каменной кладовой. Всё это было куплено в 1875 году у крестьянина Петра Стекольникова на монастырские деньги с разрешения Святейшего Синода по ходатайству игумена Николая. Рядом с церковью в 1914 году рос небольшой фруктовый сад. Закрыта церковь до Великой Отечественной войны. В годы Великой Отечественной войны церковь сильно разрушена в результате прямого попадания бомбы. В 1950 году в церкви проведены консервационные работы. 24 мая 1945 года Псковский горисполком принял решение  о передаче церкви конторе «Главсахар», это решение было отменено, и до 1998 года в церкви находилось хранилище документов Государственного архива Псковской области. После перемещения документов в новое здание в церкви начался ремонт. В 2003 году в церкви случился пожар. Благословение архиепископа Псковского и Великолукского Евсевия на открытие церкви было получено иереем Андреем Большаниным 11 сентября 2004 года. Первая служба в церкви совершена накануне праздника Введения Богородицы во Храм - 3 декабря  2004 года. 8 февраля 2007 года архиепископ Псковский и Великолукский Евсевий совершил чин освящения новых колоколов. Всего колоколов девять. На самом большом колоколе весом в 530 килограммов отлиты иконы святого Василия Великого, апостола Андрея, святителя Николая и страстотерпца Бориса. Колокола отлиты в городе Тутаев Ярославской области на деньги благотворителя. За короткий срок духовенство, благотворители, верующие люди совершили большую работу. Вот что по этому поводу сказал о. Андрей: «Когда мы начинали здесь, приделы были сильно разрушены, теперь они почти отремонтированы, утеплена крыша храма, оборудована колокольня, освобождено от мусора подцерковье, где найдено множество человеческих костей. Пробурена скважина, проведена система отопления, водоснабжения храма, сделана электропроводка, построена котельная, заменены двери и окна храма, сделан балкон-клирос, поставлен иконостас, ведутся большие ремонтные работы. Заказываем иконы, некоторые жертвуют наши прихожане. После пожара государством здесь были проведены работы стоимостью более 2 миллионов рублей, и благодаря этому восстановлены боковые стены, которые уже падали. ... Сейчас мы работаем в приделах, восстанавливаем, ремонтируем. Будем делать каменный пол. Люди жертвуют на храм, помогают, чем могут. Уже есть приход».

 В настоящее время в церкви два придела: Иоанна Богослова и Алексея человека Божия (у святителя Василия Великого был сын Алексей).

Адрес церкви: Октябрьский проспект, д. 5. Раньше этот участок проспекта назывался Сергиевской