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.
Holmens Kirke undgik de store bybrande i København i 1700-tallet og har derfor bevaret en del af sit oprindelige inventar.
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.
