В 1781 г. на полоцком кладбище был поставлен храм Покрова Пресвятой Богородицы, перестроенный из старой деревянной церкви. 21 мая 1900 г. здание Покровской церкви сгорело при пожаре, который уничтожил более 100 домов.
В марте 1901 г. в газете «Витебские ведомости» было опубликовано воззвание о пожертвовании на постройку в городе Полоцке нового Покровского храма вместо сгоревшего. Деньги собирали долго. Только в декабре 1903 г. Полоцкая православная духовная консистория издала указ о строительстве новой церкви.
21 мая 1905 г. в основание нового здания церкви поместили никелированную табличку с выгравированной надписью на лицевой стороне: «Да будет место сие свято во веки. Аминь. Во имя Отца и Сына и святаго Духа. Основася церковь в честь и память Покрова Пресвятыя Богородицы при державе БЛАГОЧЕСТИВЕЙШАГО САМОДЕРЖАВНЕЙШАГО ВЕЛИКАГО ГОСУДАРЯ НАШЕГО ИМПЕРАТОРА НИКОЛАЯ АЛЕКСАНДРОВИЧА, при святительстве же преосвященнейшаго СЕРАФИМА, ЕПИСКОПА ПОЛОТСКАГО И ВИТЕБСКАГО, при настоятеле храма сего священнике Иоанне Емельяновиче в лето от рождества Христова 1905 Мая 21 дня». На оборотной стороне был помещён «Список Членов временнаго Комитета по постройке Храма Покрова пресвятыя Богородицы во граде Полоцке»: председатель и производитель работ Генрих Фолькман, протоиерей Михаил Дубровский, Николай Ульянов, Николай Сукачев и др.
В нишу вместе с доской положили газету «Витебские ведомости» за 1901 г. и фотографию настоятеля Покровской церкви Иоанна Павловича Емельяновича.
Неизвестно точно, когда строительство нового храма было закончено. По некоторым данным, Покровская церковь была освящена в 1914 г. После Великой Отечественной войны в культовом сооружении работала кондитерская фабрика. В 1967 г. обветшавшее здание церкви было уничтожено. Найденная при сносе храма закладная доска была передана в фонды Полоцкого историко-археологического заповедника и сегодня находится в экспозиции Краеведческого музея. Церковь же была восстановлена в 2004 г.: на праздник Покрова Пресвятой Богородицы 14 октября храм был торжественно освящён.
