Mens oberst Henrik Ruse var i gang med at opføre Kastellet, udpegede han areal til to kirkegårde, en for Flåden (Holmens Kirkegård 1662) og lige overfor en for Hæren (Garnisons Kirkegård 1664).
Kirkegården, oprindelig benævnt Soldaterkirkegården, lå på et vandlidende areal og blev efter grøftegravning indviet i 1671. Under pesten blev den i 1711 udvidet med en kommunal pestkirkegård på et tilstødende areal. Kirkegården henlå forsømt, indtil der fra 1813 blev anlagt stier, beplantet og opsat mindesmærker. Efter koleraen i 1853 blev den udvidet til ca. 5 ha. Et hjørne blev indtil 1857 benyttet til begravelse for slaverne. På kirkegården hviler mange militærpersoner, og der er flere større mindesmærker for faldne i de slesvigske krige, Treårskrigen og krigen 1864, bl.a. en granitobelisk, rejst i 1869, og et mindesmærke for faldne i 1864.
