Строительство каменного храма Петра и Павла в Устюжне началось в конце XVII века. Ранее, со второй половины XVI века, на этом месте стояла деревянная шатровая церковь того же названия, которая в свою очередь, была поставлена в Петропавловском приходе города на месте двух древних деревянных храмов: холодного Во имя апостолов Петра и Павла с приделом мученицы Параскевы Пятницы, и теплого Во имя Сретения Господня. Отсюда второе название храма Сретенский.
Из описания внутреннего убранства храма 1626 года: «в нем образ местной Петр и Павел на золоте, да образ Пречистые Богородицы Одегитрия на краске, да образ Спасов нерукотвореной на золоте, образ Пречистые Богородицы Неопалимая Купина на золоте, да образ Николы Чюдотворца поясной обложен серебром, да царские двери на золоте. Над дверми деисус на трехнатцати цках (досках) и на две на десять господских праздников, да пророков на двунатцати цках поясных, все на золоте. Да паникадило медное о пяти перах (свечах). Да в пределе вверху на полатех храм святые великомученицы Парасковеи нарицаемые Пятницы. А в нем образ местной великомученицы Парасковеи на золоте в деянье, над царскими дверми деисус на девяти цках на краске стоящей».
Шатровая деревянная Петропавловская церковь стояла почти в центре города и была, в частности, известна тем, что в келье при ней жил весьма почитаемый устюжанами юродивый Афанасий Железный Посох. Строительство каменного Петропавловского храма проходило в течение конца XVII – первой половины XVIII веков и было завершено в 1748 году. Первоначально выстроили нижний теплый храм Во имя Сретения Господня с приделом Во имя Святого Иоанна Златоуста. В описании Устюжны Железопольской 1713 года было указано: «Церковь Сретения господня, каменная, теплая, а у тое церкви попов и причетнических 4 двора». Причт храма состоял из священника, дьячка, пономаря и просвирницы. Этот штат, за исключением просвирницы, был сохранен и позднее.
На следующем этапе строительства возвели второй этаж – верхний холодный храм Во имя апостолов Петра и Павла с приделом в честь Усекновения главы Иоанна Предтечи. Четверик храма имел одну главку. В середине XIX века с западной стороны прямоугольной в плане церкви пристроили трехярусную колокольню в стиле ампир. Внутреннее убранство храма, включая иконостасы, было выполнено в стиле русского барокко. Церковь Петра и Павла стала одной из трех, стоящих практически рядом храмов на правом берегу реки Мологи в центре Устюжны (совр. площадь перед мостом через Мологу в районе ул. Красных Зорь).
В городе до сих пор сохранилось предание, как три местных купца поспорили о том, кто выстроит в городе самый красивый храм. Петропавловская, Никольская и Крестовоздвиженская церкви были возведены рядом. История умалчивает, кто выиграл спор, однако известно, что спорщики не пожалели средств. Устюжна получила прекрасные памятники архитектуры, которые, увы, в дальнейшем сохранить не удалось. Петропавловский храм оставался действующим до 1935 года, а официально был закрыт на основании постановления Вологодской областной комиссии по вопросам культов от 29 декабря 1936 года. Устюженский краеведческий музей, в запасники которого передали часть икон и утвари закрытой церкви, ходатайствовал перед властями о передаче храмового здания под музейные экспозиции, однако в 1939 году оно было передано в ведение Устюженского райпотребсоюза.
В ведомости учета Вологодского Облоно о состоянии зданий и сооружений, состоящих на государственной охране, от 15 декабря 1944 года указывалось, что здание Петропавловской церкви в Устюжне «наполовину сломано и переделано и памятником в настоящее время не может считаться». До 1949 года в бывшем храме размещалась пекарня, позднее оно было уничтожено полностью.
Источник: Е.А. Воротынцева. Устюженская «Петропавловка» (об истории храма Петра и Павла (Сретенского) в г.Устюжна Вологодской обл.)