Церковь Покрова Пресвятой Богородицы находится в западной части Кремля, вплотную примыкает к восточному фасаду кремлевской стены и Покровской башни.
Первое летописное упоминание относится к 1305 году, когда посадник Семен Климович поставил каменную церковь на воротах от Прусской улицы (т. е. церковь была надвратная, пристроена к деревянной башне). В 1389 году по приказанию посадника Григория Якуновича старая церковь была разобрана и на ее месте поставлен новый храм.
В конце XVI века церковь Покрова построена заново, так как древняя кладка памятника относится именно к этому времени.
В 1692—1693 г. г. церковь Покрова перестраивается: сделаны новые барабаны, пробиты новые окна, сделана южная двухэтажная пристройка — работы велись по проекту архитектора Семена Ефимова. С этого времени церковь Покрова становится одной из главных церквей Кремля и домовым храмом новгородских воевод.
В конце XVIII века Покровская башня превращена в тюрьму, а церковь Покрова становится тюремным храмом. Вероятно, в это время устроен переход из церкви в башню.
В 1832 году храм приписан к церкви Флора и Лавра на Софийской стороне.
В 60-х годах XIX века Покровская башня и церковь приспособлены под губернский архив.
В 1889 году Покровская башня и церковь приспособлены под богадельню.
Южный придел церкви Покрова назывался приделом Рождества Иоанна предтечи, северный — приделом Святителя Николая Чудотворца.
До Великой Отечественной войны с юго-востока к церкви примыкала стенообразная трехпролетная колокольня (не сохранилась).
Памятник серьезно пострадал в годы Великой Отечественной войны (утрачена глава, крыша, часть кладки).
Памятник относится к типу бесстолпных, одноапсидных, одноглавых храмов. Четверик церкви окружен с юга и севера приделами, а с запада трапезной (притвором).
Центральная кубическая часть церкви несет на себе восьмерик, венчающийся восьмигранным барабаном с главой. С юга и севера к трапезной примыкают две пристройки, которые являются продолжением приделов. Кроме того, с юга к трапезной примыкает еще двухэтажная пристройка, тянущаяся параллельно кремлевской стене.
Фасады оформлены скромно. Восьмерик церкви имеет на углах плоские лопатки, соединенные прямыми уступами. Между лопатками расположены большие окна прямоугольной формы.
Храм является памятником архитектуры двух эпох — XVI в. и конца XVII—XIX в. в. Церковь относится к типу «восьмерик на четверике» и является одной из немногих церквей такого типа, сохранившихся в Великом Новгороде.