GPS: 57.972823 , 33.247446
В 1772 году в соответствии с генеральным планом, утверждённым Екатериной II, в Валдае было создано новое городское кладбище. Оно расположилось на окраине города, в конце Пятницкой улицы (ныне улица Луначарского). Требовалось устроить для него церковь. Местные жители не стали сооружать новое здание, а перенесли сюда деревянную церковь XVII века, освящённую в честь святых Иоакима и Анны. По сведениям церковных историков, в первой половине XVIII века валдайцы выкупили её за 30 рублей у Иверского монастыря, а находилась она на старом кладбище города.
Иоакимо-Аннинская церковь была приписана к Троицкому собору. Прихожане второго храма Валдая — Введенского — долго не имели своей кладбищенской церкви. Лишь в 1857–1858 годах было построено каменное здание с единственным куполом, которое сохранилось до наших дней. Его формы архаичны для своего времени и тяготеют к классицизму.
В конце 1930-х годов церковь закрыли, а верхний ярус колокольни разобрали. Во время Великой Отечественной войны в здании размещался военный телеграф. Святыни хранились в соседней церкви Иоакима и Анны, но в 1943 году сгорели вместе с ней. В том же году после известной встречи И. В. Сталина с церковными иерархами Петропавловская церковь была вновь открыта. Прихожане совместными усилиями восстанавливали её убранство. По воспоминаниям старожилов, иконостас был привезён из деревни Ламерьё Крестецкого района. Много усилий приложил потомственный священник из Старой Ладоги отец Николай (Листов; 1875–1946), который был переведён в Валдай сверх штата по болезни. Он похоронен рядом с Петропавловской церковью.
В 1998 году здание было признано памятником архитектуры местного значения. В 2020 году вместо разрушенной колокольни была устроена выносная звонница с новыми колоколами, отлитыми мастерами из Тутаева. В 2024 году новгородским митрополитом Львом был освящён новый купольный крест, восстанавливается колокольни церкви.