Первый каменный храм Сретения Господня постройки 1788-1801 годов, находился на том же самом месте, где сегодня стоит одноименный храм построенный в 1873 году. Закладка гранитного фундамента под храм, проводилась викарием Санкт-Петербургской епархии, преосвященным Палладием, епископом Ладожским, 21 июля 1869 года. Строительством храма в течении 4 лет занималась артель каменщиков, которую возглавлял крестьянин И. В. Волков из деревни Слобода Песочная Костромской губернии. Открытие храма и освящение бокового придела во имя святителя Павла исповедника, епископа Прусиадского было приурочено к 100-летнему юбилею города Вытегра — 20 декабря (2 янв. нов./стиля) 1873 года. Центральный алтарь храма в честь Сретения Господня освятили в 1875 году.

Два боковых придела: Успения Божией Матери и святителя Павла Прусиадского. Храм имеет три входа: западный, северный и южный. С западной стороны храма расположена шатровая колокольня. Проект Сретенского храма разработан архитектором Олонецкой губернии А. С. Четвертухиным. В храме находились иконостасы, украшенные резьбой и золочением, которые были изготовлены белозерским мещанином Н. М.Скворцовым. Кресты на купола отливали и золотили в Петербурге на заводе П. Ф.Петрова по эскизам вытегора Наумова. Основную часть средств на постройку храма завещал Вытегорский купец Павел Рулёв. Немалые денежные средства пожертвовал на постройку храма и известный вытегорский купец А. П. Игнатьев, в последствии ставший старостой прихода.

В советские годы храм закрыли, был полностью опустошен, кресты и колокола сброшены и утеряны. С 1926 года здание храма использовалось вытегорским краеведческим музеем для экспозиций и хранения экспонатов. Храм и территория церкви по частям передаются православному приходу с 1998 года.