Da kong Christian den 4. etablerede boliger for Flådens ansatte tæt på flådens base på Bremerholm, var det en del af planen at opføre en kirke.
Imidlertid blev der ikke bygget en helt ny kirkebygning, men i stedet blev flådeværftets ankersmedje fra 1562 ombygget til kirke.
Man kan stadig se ringe i fundamentet, der blev brugt til at fortøje de skibe, der skulle forsynes med ankre.
I 1619 blev kirken taget i brug og fik som menighed dels de værftsarbejdere, der boede i Skipperboderne i kvarteret omkring Laksegade, dels for byens søfolk. Da disse boliger senere flyttede udenfor byen og blev til Nyboder, var kirken stadig søfolkenens kirke, selv om den nu lå langt fra deres hjem.
Mellem smedjen og Københavns Slot blev der opført en bygning i tre etager, der var tegnet af kongens bygmester bygmester Peter de Dunckers.
Bygningen havde primært som formål at dække for udsigten, så man ikke på slottet kunne se smedjen. I bygningen var der bl.a. smedemesterbolig, toldbod, navigationsskole og Den Kongelige Mønt. Denne bygning indgik senere i kirken.
Kirken bestod fra starten af et aflangt kor, men da antallet af søfolk voksede i 1600-tallet, fik den i 1641-43 tilføjet to fløje, så den fik form som et kors. Samtidig blev kirken forhøjet.
Ombygningen blev varetaget af den kongelige bygmester Leonard Blasius.
Holmens Kirke undgik de store bybrande i København i 1700-tallet og har derfor bevaret en del af sit oprindelige inventar.
Altertavlen er udført af billedskæreren Abel Schrøder den yngre (1602-1676).
Tavlen bærer kong Frederik den 3.’s og dronning Sofie Amalie navnetræk i guld.
Navnetrækkene sidder også på prædikestolen, som også er udført af Abel Schrøder.
Den forgyldte døbefont (herunder) står midt i korsskæringen, og bærer kong Christian den 4.’s navnetræk.
I kirken hænger mange epitafier, der fortæller om de afdøde, der blev begravet under kirkegulvet.
Kirkeskibet, der hænger i loftet, er en model af Niels Juels skib Christianus Quintus, som det så ud i 1697. Skibet er udført i 1904.
Kirken havde formentlig fra starten en lille kirkegård, men i 1666 anlagdes Holmens Kirkegård udenfor voldene ved Østerport.
Her blev dog kun begravet de fattige matroser, der var i flådens tjeneste. Officerer og andre standspersoner blev gravlagt inde i Holmens Kirke.
I begyndelsen af 1700-tallet fik kirken et selvstændigt gravkapel, en kapelsal, som er en aflang tilbygning ud mod kanalen, tegnet af Johann Conrad Ernst.
Det skulle vise sig at være en god forretning for kirken, for mange ville gerne bisættes netop her.
Kapelsalen rummer især kister for gravminder og kister for søofficerer, men også enkelte civile. F.eks. ligger arkitekten C. F. Hansen og komponisten Niels W. Gade begravet her.
Blandt de mest kendte søhelte, der er gravsat i salen, er Niels Juel, som har et helt kapel for sig selv for enden af salen (herover).
Peter Tordenskjold blev først sat i krypten under kapelsalen, fordi han var omkommet i en duel, og derfor ikke kunne få plads i selve kirken. Han er dog siden flyttet ovenpå (billedet herunder).
Portalen ved kirkens hovedindgang i nordfløjen er flyttet hertil i 1872 fra Roskilde Domkirke, hvor den blev opført i 1635.
På porten er kong Christian den 4.’s navnetræk og hans motto ”Regna firmat pietas” (Fromhed styrker rigerne) samt årstallet 1635.
Ved samme lejlighed blev der opført den såkaldte skriftemålsbygning ud mod kanalen.
Udenfor kirken blev der i 1876 opstillet en statue af Tordenskjold (herunder), som er udført af billedhuggeren Hermann Wilhelm Bissen.
I midten af 2010’erne blev der opført en ny menighedsbygning i indhakket mellem kirken og kapelsalen og den nuværende kirkehave anlagt.
Udenfor kirken er der enkelte gravminder, og to mindesmærker. Det ene for søfolk, der omkom under 2. Verdenskrig (herover). Det blev rejst i 1948 og er tegnet af Viggo Sten Møller.
Det andet er udført i 2008 af billedhuggeren Karin Lorenzen, til minde om brand- og redningsfolk, der har mistet livet i tjenesten (herunder).
Ved siden af Holmens Bro liger en trappe, der i dag bruges af havnerundfarten. Den kaldes for kronometertrappen, fordi flådeskibene herfra blev forsynet med ure. I kirken havde admiralitetet et timeglas, som angav det rette klokkeslæt.
Holmens Kirke har stadig tilknytning til søens folk, og er i dag både kirke for Holmens sogn og Søværnets kirke. Den er endvidere sognekirke for en del af Københavns Indre By og kvarteret Gammelholm.
