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, og fra 1682 tog man fat på at opføre den nuværende kirke.
Den stod færdig i 1696. Arkitekten var Lambert van Haven i en stil, der ligger mellem rennæssance og rokokko.
Kirken er sædvanlig ved at være bygget i korsform, hvilket ikke er almindeligt i Danmark.
Kirken havde ikke fra starten noget spir. Lambert døde før kirken blev taget i brug og nåede ikke at få tegnet et spir. Det fik den først i 1750, hvor arkitekten Laurids de Thurah tegnede det snoede spir, som kirken i dag er mest kendt for.
Det fortælles, at Thurah kastede sig ud fra tårnet, fordi det var snoet den forkerte vej i forhold til kongens ønske. Det er og ikke en sand historie, idet Thurah døde af naturlige årsager syv år efter spiret var færdig.