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

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

В 1930-х годах церковь закрыли. Здание храма использовалось под жильё, дискотеку, бильярд...

В настоящее время церковь передана верующим.