Kirkebygningen er den tidligere ankersmedje fra 1562, der lå i forbindelse med skibsværftet på Bremerholm.
Man kan stadig se ringe i fundamentet, der blev brugt til at fortøje de skibe, der skulle forsynes med ankre.
Mellem smedjen og slottet opførte man en bygning i tre etager, opført af kongens bygmester kongens bygmester Peter de Dunckers. Den 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.
I smedjen stod Danmarks første dampmaskine, der blev installeret i 1791.
I 1617 blev kirken indrettet til kirke dels for 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 beboernes kirke, selv om den nu lå langt fra deres hjem.
Antallet af søfolk voksede i 1600-tallet og derfor blev kirken blev udvidet i 1641-1643 af den kongelige bygmester Leonard Blasius. Den blev omdannet til en korskirke ved at tilføje to sidefløje.
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 kirken.
I begyndelsen af 1700-tallet fik kirken et gravkapel, en kapelssal, 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.
I kapellet ved Holmens Kirke ligger bl.a søheltene Peder Tordenskjold og Niels Juel begravet. Udenfor kirken blev der i 1876 opstillet en statue af Tordenskjold, udført af billedehuggeren Hermann Wilhelm Bissen.
Holmens Kirke undgik de store bybrande i København i 1700-tallet og har derfor bevaret en del af sit oprindelige inventar.
I 1871-1873 fik kirken ny hovedport, som stammer fra Roskilde Domkirkes vestparti. På porten er kong Christian den 4.’s navnetræk og hans motto ”Regna firmat pietas” (Fromhed styrker rigerne) samt årstallet 1635.
Udenfor kirken ligger ved siden af Holmens Bro 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 tilknytning til søens folk, og er i dag både kirke for Holmens sogn og Søværnets kirke.
