Церковь эта, ныне принадлежащая общине старообрядцев, построена была как православная в 1914–1918 годах. В 1914 году епархиальная газета Церковно-общественный вестник сообщила, что 17 сентября, в 1 час дня на поле за Вдовьим домом, между Бугровским старообрядческим кладбищем и бывшим ипподромом, совершена закладка новой кладбищенской церкви.
Молебствие совершал преосвященнейший Иоаким в сослужении с городским духовенством. На молебне присутствовали высшие чины городской администрации, заступающий на место городского головы М.И. Будилов, член управы В.И. Смирнов, другие чиновники, а также представительница рода Рукавишниковых В.М. Бурмистрова. Рукавишниковы и Акифьевы пожертвовали деньги на строительство церкви и пригласили архитектора Императорского Двора В.А. Покровского. Он спроектировал Кладбищенский комплекс каменных зданий, включивший церковь, дом ее причта, келейку могильщиков, высокую кирпичную ограду с квадратными декоративными башенками по углам и въездом ворот.
Решением Горьковского Облсовета от 1 ноября 1940 года церковь была закрыта, о чем церковному совету сообщили 20 ноября 1940 года. Не знавшие еще о закрытии их церкви верующие 12 ноября 1940 года обещали райсовету, что любой ценой погасят накопившиеся за октябрь священниками Архангельским и Свиридовым задолженности и просили продлить регистрацию священников до 1 января 1941 года.
Но 6 декабря 1940 года Ждановский райисполком постановил служителям культа Архангельскому и Свиридову регистрацию аннулировать. А церковь с 9 декабря 1940 года закрыть, т.к. церковный совет задолжал свыше 100 тыс. руб. налога и здания требует капремонта, отваливается штукатурка и т.д. Община немедленно 19 декабря 1940 гожа написала в Ждановский райсовет протест о неправильности закрытия церкви, налоги к тому времени уплатили, и состояние церкви было нормальное, штукатурка не падала. Однако Горьковский облисполком утвердил решение Ждановского райисполкома о закрытии церкви. 21 декабря 1940 года постановил закрыть Покровскую церковь в Ждановском районе с последующим ее переоборудованием под клуб.
27 января 1941 года Президиум ВС РСФСР решение Горьковского облсовета утвердил и здание церкви передал Ждановскому райисполкому для переоборудования под клуб, с условием согласовать оборудование с отделом по охране памятников Управления по делам искусств при СНК СССР. Ждановский райисполком решением от 6 февраля 1941 года передал помещение Новокладбищенской церкви Промкомбинату для размещения в нем клуба и мастерских. 14 апреля 1941 года Облисполком утвердил решение Ждановского райсовета и отдал здание церкви Промкомбинату.
До 1964 года зданием церкви владела Горьковская чулочно-трикотажная фабрика производственного объединения им. Клары Цеткин. 26 августа 1964 года фабрика передала помещение церкви на Пушкинском кладбище в Приокском районе площадью 823 кв. м и прилегающей к ней территории с баланса на баланс в Бюро похоронного обслуживания при Управлении благоустройства. К тому времени здание требовало капитального ремонта, всего от отопления до оконных переплетов, дверей и полов.
В таком состоянии здание церкви 28 августа 1964 года было решением Горьковского горисполкома передано с баланса Управления благоустройства и коммунальных предприятий на баланс Горьковской старообрядческой общине. Успенская старообрядческая община окончила основные работы по восстановлению церкви к 10 января 1965 года.
В марте 1965 года здание Успенской старообрядческой церкви на ул. Суетинской снесли. Здание церкви на Пушкинском кладбище предоставили старообрядцам в бесплатное пользование взамен сносимого. С тех пор Новокладбищенская церковь, старообрядческая.
