Храм святых первоверховных апостолов Петра и Павла в городе Плёс был построен в 1845 году на месте более древнего деревянного храма, существовавшего здесь с XVI века. Деревянная церковь, упоминаемая в писцовых книгах, служила кладбищенским храмом на погосте Петропавловской горы. В 1827 году возник конфликт между горожанами и помещиком Мячковым, пытавшимся присвоить храмовые земли, но плесский городской голова Гавриил Частухин и купец Андрей Солодовников отстояли территорию и инициировали строительство каменного храма.
Каменная церковь была освящена в 1845 году. В неё перенесли часть икон XVII века из прежнего деревянного храма, включая образ Спаса Нерукотворного 1696 года с вкладной надписью Нефеда Савинова. Храмовая территория включала два кладбища: древнее при деревянной церкви и новое в ограде каменного здания. В архитектурном отношении здание представляло собой односветный кирпичный храм прямоугольной планировки с трапезной и колокольней, стены которого были покрыты известковой обмазкой.
В конце XIX века настоятелем храма был священник Иаков Успенский, прослуживший здесь четверть века. В 1887 году он обратился в Императорское московское археологическое общество с просьбой обследовать старинный деревянный храм, что привлекло внимание к памятнику. В 1888-1889 годах художник Исаак Левитан, вдохновлённый видом деревянной церкви, создал в Плёсе несколько картин, включая «Над вечным покоем», где изображён этот храм.
Деревянный Петропавловский храм сгорел в 1903 году. В 1970-е годы на гору Левитана перенесли аналогичный по архитектуре Воскресенский храм 1699 года из села Билюково. Каменная же Петропавловская церковь в XX веке лишилась куполов, колокольни и интерьерных росписей. Сохранился основной объём здания, включающий храмовую часть, трапезную и первый ярус колокольни. Фасады храма сохраняют элементы первоначального декора: кирпичные наличники окон с прямоугольными нишами, пояс ребристых сухариков и треугольный сандрик над западным входом.