På den oprindelige plan for Christianshavn var der tegnet en kirke ved Christianshavns Torv.
Den blev dog ikke realiseret her, og i bydelens første år måtte indbyggerne bruge Holmens Kirke.
I 1640 blev der bygget en midlertidig kirke, der lå lidt syd for den nuværende, og fra 1682 tog man fat på at opføre den egentlige kirke. Den stod dog først færdig i 1696, for grunden måtte først fyldes op og funderes.
Arkitekten var Lambert van Haven som tegnede kirken i nederlandsk barokstil. Den er bygget i korsform, hvilket ikke er almindeligt i Danmark.
Grundplanen er fem store kvadrater, med mindre kvadrater indskudt i hjørnerne, hvor de mødes. Dermed bliver kirken fuldstændigt symmetrisk.
Facaderne er præget af de kraftige pilastre, altså søjler, der ikke egentligt bærer konstruktionen, men mest er dekoration.
Hovedindgangen er gennem en portal i kirkens vestside. Her sidder kong Christian den 5.’s navnetræk og hans valgsprog “Pietate et justitia” (Fromhed og retfærdighed).
Kongens monogram sidder også i krydshvælvet over kirkerummet.
Kirkerummet er højt og måler 36 meter fra gulv til loft. Interiøret er præget af barokken og kirken regnes for den mest gennemførte barokkirke i Danmark.
Det mægtige marmoralter er udført af den svenske arkitekt Nicodemus Tessin den yngre (1654-1728). Motivet er Jesus, der bliver trøstet af engle i Getsemane have. I siderne står figurer, der symboliserer de to begreber fromhed og retfærdighed, der indgik i kirkebyggeren, Christian den 5.s, motto.
Alterbordet er omgivet af de græske gudinder, fromheden og retfærdigheden.
På skranken foran koret sidder seks engle udført i træ, men malet så de ligner marmor.
Prædikestolen er udført af arkitekten Casper Friederich Harsdorff, billedhuggeren Johannes Wiedewelt og maleren Peder Als.
Døbefonten er placeret i et lille, lukket kapel (herunder). Den blev skænket til kirken af grevinde Helene von Viereck. Hun er bisat i en hvælving under orglet sammen med sin søn, som hun fik sammen med kong Frederik den 4.
Et krucifiks stammer muligvis fra den første kirke på Christianshavn.
Orglet er båret af to elefanter som en reference til kong Christian den 5. indstiftelse af elefantordenen. Kongens buste er nærmest bygget ind i orglets facade ud mod kirkerummet.
Overover orglet sidder to urskiver, der viser tidens gang i henholdsvis timer og minutter.
Kirken havde ikke fra starten noget spir. Lambert døde før kirken blev taget i brug og det spir, han havde tegnet (herover), blev ikke bygget.
Det snoede spir, som kirken er mest kendt for, fik kirken først i 1750. Det blev tegnet af arkitekten Laurids de Thurah. Spiralsnoningen er formentlig inspireret af Sant’Ivo alla Sapienza-kirken i Rom.
Det fortælles, at Thurah kastede sig ud fra tårnet, fordi spiret var snoet den forkerte vej i forhold til kongens ønske. Det er dog ikke en sand historie, idet Thurah døde af naturlige årsager syv år efter, at spiret var færdigt.
Øverst på tårnet står figurer af de fire evangelister.
Toppen af spiret er afsluttet med en mandsfigur, og måler næsten 87 meter. Det er ved hjælp af en udvendig trappe muligt at komme næsten helt op i toppen af spiret.
På Christianhavn boede der fra 1600-tallet en del tysktalende, og derfor blev der i Vor Frelsers Kirke holdt gudstjenester både på dansk og tysk. Midt i 1700-tallet ønskede den tyske menighed dog sin egen kirke, og derfor blev der i bydelen opført endnu en kirke, der fra begyndelsen hed Frederiks Tyske Kirke, men senere blev omdøbt til Christians Kirke.
Blandt kirkens præster var forfatteren og salmedigteren N. F. S. Grundtvig, der virkede her i 1820’erne indtil han på grund af en strid trådte ud af folkekirken.