Den første kirke her blev formentlig opført i 1200-tallet under navnet Sankt Peder.
Kirken var i middelalderen den en af Københavns fire kirker. De øvrige var Sankt Clemens Kirke, Sankt Nikolaj Kirke og Vor Frue Kirke.
Tårnrum, kor og skib er formentlig fra omkring 1450 og kirken er dermed den ældste, bevarede i det indre København.
Ved Reformationen blev kirken nedlagt og i en periode brugt som kanonstøberi.
Som en følge af reformationen fik menighederne lov at bruge deres modersmål som kirkesprog, og da der i 1575 blev oprettet en tysk menighed i København, var det naturligt, at den fik overladt den “overskydende” kirke i byen.
Bygmester Hans van Steenwinckel (den ældre) (1550-1601) gav den sit nuværende udseende ved en ombygning.
Flere udvidelser måtte til i 1600-tallet, ikke mindst fordi der kom mange tyske håndværkere til byen i forbindelse med kong Christian den 4.’s byggerier.
Ved den store bybrand i 1728 blev kirken hårdt ramt, men genopbygget. Tårnet blev forsynet med spir. Det var måske Johan Boye Junge (1735-1807) der tegnede spiret, eller måske var det Nikolaj Eigtved (1701-1754), der selv ligger begravet ved kirken.
Den store indgangsportal ud mod kirkens gård, er opført i 1731 efter tegning af Didrik Gercken (1692-1748).
Under englændernes bombardement af København i 1807, lykkedes det at redde kirken – ikke mindst fordi graveren lagde våde klude på de steder, hvor brandbomberne ramte.
Ved siden af kirken ligger et anseeligt gravkapel. Det blev opført 1681-83 og var ikke kun beregnet for de fornemste i menigheden, men for alle dens medlemmer. Arkitekten bag kapellet menes at være Hans van Steenwinckel den 3. (1639-1700).
Kapellerne er særlige ved, at kisterne er lagt i krypter under gulvet. Enkelte prominente aføde har deres egne sidekapeller, der er aflukket med smedejernsgitre.
Kirken har dog også haft begravelser udenfor, dels på den almindelige kirkegård, dels på den særlige fattigkirkegård, som lå ud mod Larslejsstræde.
