В 1871 город купил у гр. А. П. Шувалова за 24 тыс. руб. лесистое место в трех верстах от станции Парголово для нового кладбища. Оно было открыто четыре года спустя, и от станции к нему проложили железнодорожную ветку. В 1887 на кладбище создано военное, а в 1910 - католическое отделение. Имелся также небольшой лютеранский участок и участок с часовней, где хоронили погибших полицейских и пожарных. Деревянная с шатровой колокольней церковь, которая дала кладбищу название, была заложена как временная 29 августа 1874 по проекту арх. П. Ю. Сюзора и через сто дней - 6 декабря - освящена прот. Иоанном Исполатовым. Она обошлась в 150 тыс. руб. Иконы в одноярусном иконостасе написал акад. Н. А. Лавров. Впервые в церковном строительстве была применена новинка - водяное отопление. Через несколько лет, 29 мая 1879, в церкви освятили дополнительный Петропавловский придел.
Газеты писали: "Внутренность церкви представляет соединение вкуса и простоты -дубовый резной иконостас, хрустальные люстры, принадлежности богослужения - всё в совокупности хотя и не роскошно, но как нельзя более соответствует скромному сельскому храму". Хотя в 1899 храм отремонтировали, его состояние оставалось аварийным. Кроме того, он был чересчур тесен. Поэтому в марте 1907 проф. А. Н. Векшинскому был поручен проект еще одной деревянной церкви на кладбище, а В. Н. Боброву - план каменного трехпридельного храма. Однако дальше замысла дело не двинулось, хотя средства были отпущены. В городе, на Чугунной улице, стояла часовня-покойницкая, где гробы находились до отправки на кладбище по особой железнодорожной ветке. В Духов день из церкви в деревню Новоселки шел крестный ход. Летом 1913 на участке Воспитательного дома была освящена часовня равноап. Марии Магдалины. В конце 1932 ее закрыли.
С освящения до своей смерти в 1913 в церкви служил прот. Иоанн Петрович Прощаницкий. Затем недолгое время священствовал о. Иоанн Павлович Киселев, бывший псаломщик Андреевского собора в Кронштадте, хорошо знавший о. Иоанна Кронштадтского. Последним до революции настоятелем был прот. Сергий Варфоломеевич Воскресенский.
Церковь была закрыта и затем снесена. Мариинская часовня стоит полуразрушенной.
Антонов В.В., Кобак А.В. Святыни Санкт-Петербурга. СПб., 2010, с. 389