Da Nørrevold og Østervold blev udbygget i 1870’erne og 1880’erne, hørte området endnu under Sankt Johannes Sogn på Østerbro.
Men med det stigende befolkningstal, var der behov for en kirke for kvarterets beboere. En kirkebygningskomité havde foreslået opførelsen af to nye kirker i byens hastigst voksende områder. Derfor byggedes Hellig Kors Kirke på Nørrebro, men da man skulle i gang med den næste kirke i voldkvarteret, var midlerne til formålet brugt.
Pastor Julius Steen fra Sankt Johannes Kirke satte derfor en indsamling i gang, og det lykkedes at skaffe tilstrækkeligt med midler, så der kunne bygges en kirke på hjørnet af Østre Farimagsgade og Gothersgade.
Arkitekten var Martin Borch (1852-1937) og han tegnede en kirke, der er næsten middelalderlig i sin byggestil. Fordi hjørnegrunden var ret lille, blev korbygningen lagt vest for tårnet, som fik plads tæt på krydset mellem de to store veje, og her ligger det som et meget synligt vartegn for kirken, for dem.
Bagtil opførtes en menighedsbygning, der blev forbundet med kirken, så der opstod et næsten klosteragtigt anlæg.
Åbenbart var pengene så rigelige, at kirken blev anset for at være lidt for ekstravagant. Murstenene blev lagt i skifter som i middelalderen, og stenene var håndstrøgne. Det fortælles, at Martin Borch lod høns spadsere på de nylavede sten, så deres fødder lavede mønstre i dem.
Hovedindgangen er fra Østre Farimagsgade, og er gennem en portal med løver, udført af billedhuggeren Anders Bundgaard.
Kirkens indre er holdt i en senromantisk stil, der matcher Kommunehospitalet, som den er nabo til.
I dag er kirken en del af Vor Frue Kirkes sogn.