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 Garnisions 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.
Kirkegården udenfor Østerport kaldtes bl.a. matroskirkegården, bådsmandskirkegården og skibskirkegården.
Under pestepidemierne i 1700-tallet, hvor man måtte 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. Sikkert af denne grund, er en lang række kendte personer, ikke mindst kunstnere, begravet på Holmens Kirkegård.
I 1800-tallet var det derfor nødvendigt at udvide kirkegården flere gange.
På Holmens Kirkegård står en obelisk, udført af billedhuggeren Johannes Wiedewelt til minde om de mere en 500 omkomne, i “slaget på reden”.
Holmens Kirkegårds kapel blev brændt ned af militæret under englændernes bombardement af København i 1807. Kapellet lå indenfor de beskyttelsezoner, 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.