Небольшой деревянный храм с маленькой, почти декоративной, луковичной главкой и невысоким шатром звонницы возведен в 1993 – 1994 годах. Освящение церкви состоялось 28 августа 1994 года. Рядом с церковью возведена маленькая часовня с луковичной главкой.

Приход церкви Петра и Павла в Шуваловском парке, к которой приписан Никольский храм, приступил к возведению на кладбище, рядом с деревянными церковью и часовней, также каменного храма в честь Успения Божией Матери.

Прежде здесь, на основанном в 1874 году кладбище, существовала до 1937 года деревянная Успенская церковь, построенная по проекту П. Ю. Сюзора. Этот храм был заложен 29 августа 1874 года. Строительство церкви продолжалось всего сто дней. Освящение её состоялось 6 декабря того же года в присутствии градоначальника Л. Рудатовского, а регулярные богослужения начались в 1875 году.

С гравюры 1875 г.

Убранство церкви обошлось в пять с половиной тысяч рублей. 22 иконы, написанные на холсте, были одной из последних работ академика портретной и исторической живописи Н. А. Лаврова, работавшего и над образами для московского храма Христа Спасителя. Спустя пять лет, 29 мая 1879 года был освящен небольшой придел во имя св. апостолов Петра и Павла. Кладбищенский храм был небольшим - в нем помещалось не более двенадцати гробов, тогда как в 1904 году на кладбище хоронили до 35 человек ежедневно.