Oprindeligt skulle kirken for hele bydelen Christianshavn have ligget på Christianshavns Torv.
I stedet blev Vor Frelsers Kirke opført i 1680’erne. Der mange tysktalende i bydelen gjorde, at man havde behov for en kirke specielt for dem. I 1750’erne begyndte man derfor på opførelsen af en ny kirke for enden af Strandgade.
Den blev navngivet efter kong Frederik den 5. og hed i begyndelsen Frederiks Tyske Kirke. Senere blev den omdøbt til Christians Kirke, for at undgå forveksling med Frederiks Kirke (Marmorkirken) i København. Der var tysk menighed på Christianshavn indtil 1886.
Kirken er tegnet af arkitekten Nicolai Eigtved (1701-1754) og kirkerummet er udformet ligesom en teatersal, hvor siddepladserne er anbragt i gallerier. Eigtved har givet navn til Nicolai Eigtveds Gade, der går på nordsiden af kirken.
Opførelsen blev bl.a. finansieret gennem et statsligt lotteri, og kirken kaldes derfor også ”lotterikirken”.
I takt med at Burmeister & Wains skibsværft på det sydlige Christianshavn optog større og større arealer, blev kirken efterhånden helt omgivet af B&W’s bygninger. Kortet herunder viser situationen i 1970.