Kirken er yngre end Korsgade, som den ligger for enden af.
Den er opført 1887-1890 efter tegninger af arkitekt Hermann Baagøe Storch (1839-1922) i en nationalromantisk stil.
Den blev planlagt af Københavns Præstekonvent, der i 1886 besluttede at opføre en kirke i det såkaldte “rabarberkvarter” omkring Rantzausgade og Kapelvej.
Københavns Kommune stillede grunden til rådighed, og der var en del af den tidligere kolerakirkegård, som lå i den sydligste del af Assistens Kirkegård.
Midlerne til opførelsen kom dels fra kommunen, dels fra en indsamling, der bl.a. fik bidrag af mange lokale håndværksmestre.
Kirken blev ret rummelig, for den havde fra starten plads til 1600 kirkegængere. Senere er kapaciteten reduceret til omkring 600.
Altertavlen blev tegnet af kirkens arkitekt, H. B. Storck. Prædikestolen er udført af H. C. Berg. Valdemar Koch tegnede døbefonten, som er udsmykket med figurer, der forestiller de fire evangelister.
Tårnet er 55 meter højt.
Hellig Kors Sogn var fra begyndelsen et selvstændigt sogn, der blev udskilt fra sognet, der hørte til Sankt Johannes Kirke, og som på det tidspunkt havde mere end 60.000 indbyggere.
Fra 1999 er Hellig Kors Kirke en del af Blågårds Sogn.
Tidligere havde sognet Bethlehemskirken i Blågårdsgade som filialkirke, men den blev i 1917 udskilt og fik sit eget sogn.
I tilknytning til kirken ligger menighedsbørnehaven Linden (herunder).
