Была первой в истории города кладбищенской. Ее строительством отмечен особый этап развития духовной жизни. Приступая к коренному переустройству городов России на регулярной основе, Комиссия о каменном строении Санкт-Петербурга и Москвы в 1763 году встретилась с почти неодолимыми трудностями - возле приходских церквей издревле располагались погосты. Прокладка под ним улиц вызывала, естественно, взрывы негодования. После долгих прений предписанием Сената от 17 ноября 1771 года (подтверждено Синодом 29 ноября 1771 года) указывалось, чтоб впредь "по городам при церквах никого не хоронили, а отвели бы для этого специальные кладбища за городом на выгонных землях".

В 1775 году в Нижнем Новгороде в полуверсте за Варварской решеткой отвели для общегородского кладбища свободное место, поставили часовню и обнесли оградой (современный парк Кулибина). В 1780 году при начале перепланировки Нижнего Новгорода была уничтожена стоящая под Кремлевским холмом в полугоре каменная Петропавловская церковь. Ее прихожане, купцы Егор и Александр Неудакины, чтоб сохранить престол церкви, предложили выстроить за свой счет каменный храм на кладбище. Проект заказали первому губернскому архитектору Я.А.Ананьину.

В декабре 1781 года здание было вчерне отстроено, и Нижегородский епископ Антоний освятил алтарь придела в честь Константина и Елены. В 1783 году был освящен придел в честь Василия Парижского и Петра Александрийского. В 1785 году епископ Дамаскин освятил главный престол в честь Петра и Павла. Как большинство кладбищенских церквей, ее называли также Всесвятской, а по главному престолу - Петропавловской.

Здание бесстолпное, со световым барочных форм восьмериком на четверике, трапезной и трехъярусной колокольней над западным входом (тип "корабля"). Барочные оконные наличники вытесаны из кирпича. Это единственный сохранившийся в Нижнем Новгороде памятник русского барокко второй половины XVII века (не сохранилась колокольня, перестроены западная и алтарная части).