Была первой в истории города кладбищенской. Ее строительством отмечен особый этап развития духовной жизни. Приступая к коренному переустройству городов России на регулярной основе, Комиссия о каменном строении Санкт-Петербурга и Москвы в 1763 г. встретилась с почти неодолимыми трудностями - возле приходских церквей издревле распологались погосты. Прокладка по ним улиц вызывала взрывы негодования. После долгих прений предписанием Сената от 17 ноября 1771 г. указывалось, чтоб впредь земли под кладбища отводились за территорией городов.
В 1775 г. в Н. Новгороде в полуверсте от границы города (отмеченной Варварской часовней) было отведено место под кладбище, построена часовня(ныне это парк им. Кулибина). В 1780 г. при перепланировке Н. Новгорода была снесена стоявшая под Кремлевским холмом Петропавловская церковь. Ее прихожане, купцы Егор и Александр Неудакины, чтоб сохранить престол церкви, предложили выстроить за свой счет каменный храм на на кладбище. Проект заказали первому губернскому архитектору Я.А. Ананьину. В декабре 1781 г. здание было отстроено и Нижегородский епископ Антоний освятил алтарь придела в честь Константина и Елены. В 1783 г. был освящен придел в честь Василия Парижского и Петра Александрийского. В 1785 г. епископ Дамаскин освятил главный престол в честь св. Петра и Павла. Как большинство кладбищенских церквей, ее называли также Всехсвятской, а по главному престолу - Петропавловской.
Здание бесстолпное, со световыми барочных форм восмериком на четверике, трапезной и трехъярусной колокольней над западным входом. Барочные оконные наличники вытесаны их кирпича. Это единственный сохранившийся в Н. Новгороде памятник русского барокко второй половины XVIII в. В годы советской власти была разрушена колокольня, перестроены западная и алтарная части. В настоящее время храм восстанавливается.