Samtidig med opførelsen af Kastellet, blev der udenfor voldanlægget, på hver sin side af Østerbrogade, afsat plads til anlæg af to kirkegårde til brug for henholdsvis Hæren og Flåden.
Flådekirkegården fik plads på sydsiden og navnet Holmens Kirkegård, efter Flådens havn og værft på Bremerholm. Hærkirkegården – eller Garnisons Kirkegård – lå på nordsiden.
Kirkegårdens navn skyldes, at soldaterne i København lå i garnison indenfor byens volde.
I forbindelse med anlægget af bydelen Ny-København, projekteredes en kirkegård der skulle ligge uden for Østerport, hvor man havde planer om et kirkebyggeri.
Kirken blev ikke bygget, men kirkegården lå der, og blev i de første mange år brugt til begravelse af soldater.
Området var ikke særligt egnet til begravelser, fordi det var lavliggende og fugtigt. I 1671 fik man dog arealet indhegnet og reguleret, så kirkegården formelt kunne indvies.
Kirkegården var ikke fra starten knyttet til en kirke, men blev i 1700-tallet begravelsesplads for Garnisons Kirke, der var hærens. Indtil 1723 blev den slet og ret kaldt for soldaterkirkegården, og derefter fik den sit nuværende navn.
Under pestepidemien i 1711 måtte man bruge al den tilgængelige, indviede jord i København for at begrave ofrene for sygdommen. Ved siden af Garnisons Kirkegård blev der endda anlagt en særlig pestkirkegård.
I løbet af 1700-tallet blev kirkegården også brugt til at begrave civile københavnere, men da den lå udenfor byen var den ikke særligt attraktiv. Det blev regnet for finere at blive begravet tæt op af en kirke, og allerbedst at blive gravlagt inde i kirken.
Ud mod Østerbrogade lå ved siden af Garnisons Kirkegård også fattigkirkegården.
På Garnisons Kirkegård står et gravminde over faldne i krigen i Slesvig i 1864 (herunder).
Kirkegårdens kapel er tegnet af arkitekten Holger Jensen (1918-2004) og er opført i 1994.
Ved kapellet står en skulptur (herunder) udført af billedhuggeren Hein Heinsen, der symboliserer overgangen fra korsfæstelse til opstandelse.
