Trinitatis Kirke i det indre København er én af byens ældste kirker. Midt i 1800-tallet blev den også kirke for den opvoksende bydel Ny-København.
Her var Frederiks Kirke (Marmorkirken) under opførelse, men det varede mange år at få den bygget færdig.
En del af sognet lå udenfor søerne, og her havde man allerede i 1861 indviet Sankt Johannes Kirke på Nørrebro.
Man besluttede at opføre en ny kirke i Trinitatis Sogns nordlige distrikt omkring Nyboder. Kvarteret, der blev opført fra 1600-tallet og frem, havde aldrig fået sin egen kirke. Den planlagte Sankt Anna Rotunda kirke, der skulle have været Nyboders kirke, blev aldrig fuldført.
Den nye kirke i det nordlige distrikt blev tegnet af arkitekt J.E. Gnudtzmann (1837-1922) og opført i starten af 1870-erne. Staten, der ejede arealet ved Nyboder, skænkede grunden.
Der var udskrevet en arkitektkonkurrence, hvor Gnudtzmanns forslag fik andenpræmien. Hans forslag var en kirke efter norditalienske forbilleder, og arkitekten fandt måske også inspiration i Universitetsbiblioteket, der var bygget 10 år tidligere. Kirken var et af Gnudtzmanns første arbejder i København.
Sankt Pauls Kirkes opbygning som en treskibet basilika er usædvanlig i København.
Med sit 47 meter høje tårn rager kirken markant op over Nyboders lave huse.
