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.
Hærkirkegården – eller Garnisons Kirkegård – lå på nordsiden, mens flådekirkegården fik plads på sydsiden og navnet Holmens Kirkegård, efter Flådens havn og værft på Bremerholm.
Holmens Kirkegård blev anlagt i 1666 og blev i starten brugt til at begrave fattige matroser, der ikke havde råd til en mere fornem placering i Holmens Kirke. Ved selve kirken var der en kirkegård, og man havde også en begravelsesplads lige udenfor Nørreport.
Under pestepidemierne i 1700-tallet måtte man tage al den tilgængelige, indviede jord i brug til begravelsespladser for de mange ofre for sygdommen. Mange hundrede blev derfor lagt i jorden på Holmens Kirkegård.
Efterhånden ændredes reglerne for kirkegårdens brug dog også sådan, at også Flådens højerestående officerer, skulle bruge den. De brød sig dog ikke særlig meget om, at de skulle i jorden helt udenfor byen, og ovenikøbet på en kirkegård, der ikke var indhegnet – så kreaturer og andre dyr kunne gå lige ind.
I slutningen af 1700-tallet kom der hegn om kirkegården og den blev beplantet med træer. I takt med, at de mere velstående københavnere fik landsteder på Østerbro, blev det nemlig attraktivt at blive begravet herude.
I kirkegårdens første tid var det ikke tilladt at opsætte monumenter på gravene, men med dens nye “klientel”, blev det nu oftere efterspurgt af de pårørende.
Da Holmens Kirkes præst, Laurids Smith, havde ønsket at blive begravet sammen med sine sognebørn, blev bestemmelsen omgået ved at der opstillet et monument for ham udenfor hovedindgangen.
Efter “slaget på reden” – søslaget udenfor Københavns Havn i 1801 – blev de omkomne begravet her, og det styrkede også kirkegårdens status, at man kunne komme til at ligge sammen med søhelte. Et monument for de faldne i slaget er udført af billedhuggeren Johannnes Wiedewelt.
Ikke mindst personer, der var kendt i offentligheden, f. eks. kunstnere, blev begravet på Holmens Kirkegård.
I 1800-tallet var det derfor nødvendigt at udvide kirkegården flere gange.
Holmens Kirkegårds kapel blev brændt ned af militæret under englændernes bombardement af København i 1807.
Kapellet lå indenfor de beskyttelseszoner, som omgav byen, og de måtte ikke have faste bygninger.
Der blev opført et nyt efter krigen, og det afløstes af det nuværende, der er tegnet af arkitekten Ludvig Fenger (1833-1905) i 1902.
Kapellet er et utradtionelt bygningsværk, der mest af alt ligner en norsk stavkirke.
Det var også Fenger, der i 1884 tegnede kirkegårdens inspektørbolig ved indgangen ud mod Lille Triangel ved Dag Hammerskiölds Allé.
I dag er Holmens Kirkegård den ældste kirkegård i brug København.