The name comes from the church of John the Apostle, (Russian: Иоанн Богослов, Ioann Bogoslov), which from the early 18th century had a burial ground attached, mostly for those who died in the nearby military hospital. This site was some 2.5km south of the present cemetery, at what is now the intersection of Arsenalnaya Street[ru] and Mineralnaya Streets[ru]. The church and cemetery were closed in 1788 and the land sold off into private ownership. In 1841 the city acquired a new plot of land for a cemetery, and named it after the previous one. In 1844, the Most Holy Synod approved the building of a new stone church, but no funds were available. In 1853-1854 a small two-storey chapel was built.
In 1915–1916, a new wooden three-fronted church of John the Apostle was built at the cemetery to the design of architect Viktor Bobrov[ru]. The church was closed during the Soviet era, and finally looted and demolished in 1938, along with part of the cemetery, as it lay within an area closed off for military purposes. In Soviet times the cemetery became the burial place of many prominent scientists, cultural figures, and military officials. It was also the site of several mass graves of those who died during the siege of Leningrad. These are found in the northern part of the cemetery, marked by a hill topped with a small obelisk. In October 2000, a newly rebuilt wooden church of John the Apostle was consecrated.