Da Nørrebro havde fået sin første kirke, Sankt Johannes, i 1861, gik der ikke lang tid, før dens præst, Rudolf Frimodt, tog initiativ til at bygge endnu en kirke i bydelen.
Befolkningstallet voksede hurtigt, og i 1870’erne begyndte boligudviklingen udenfor Jagtvej, på det ydre Nørrebro.
Frimodt samlede penge ind, og i 1874 blev den nye kirke ved Nørrebrogade. Grunden blev skænket af lensbaron Løvenskjold, som havde ejendommen Kirstinedal i nærheden.
Den første kirke på Ydre Nørrebro blev opkaldt efter Sankt Stefanus, som var én af de fattigforsørgere, der nævnes i Bibelen. Han blev henrettet med stenkast og derfor martyr. Måske lå der i navnet en hentydning til den fattige befolkning på Nørrebro.
Sognet havde mange fattige og arbejderfamilier, og kirken påtog sig et væsentligt, socialt arbejde blandt dem.
Kirken gav senere navn til Stefansgade, som tidligere hed Havremarksvej.
Sankt Stefans Kirke blev tegnet af arkitekten Ludvig Knudsen (1843-1924) og bygget i romansk stil.
Tidsskriftet Illustreret Tidende skrev i 1873 om kirkebyggeriet, at de fattige i det såkaldte Lygtevejskvarter, ville kunne glæde sig over den nye kirke, der var under opførelse mellem Jagtvej og Lygtekroen.
Kirkens altertavle er udført af Anton Dorph (1831-1914). Motivet er Jesus, der besøger Martha og Maria, og det var to frøkener fra Blågård, der stod model.
I våbenhuset hænger et relief, udført af billedhuggeren Theodor Stein (1829-1901). Her er også en mindetavle for pastor Rudolf Frimodt.
Til 25 års jubilæet i 1924 fik skænket mosaikruder, der blev udført af Johannes Kragh (1876-1946). Kirken har et maleri, der forestille Sankt Stefans død.
Omkring 1900 var den nordlige del af sognet under udbygning, og området mellem Nørrebrogade og Tagensvej blev udskilt som et selvstændigt kirkedistrikt.
Først kaldtes det Tagens Sogn, men efter indvielsen af Kingos Kirke i 1910, fik det navn efter den.
Ved Frederikssundsvej blev Kapernaumskirken opført i 1890’erne og blev midtpunkt i sit eget sogn, der blev udskilt fra Stefans.
Også området omkring Jægersborggade blev skilt ud og her opførtes fra 1914 Anna Kirke.