Gaden er opkaldt efter Sankt Stefans Kirke, der ligger på hjørnet af Stefansgade og Nørrebrogade.
Kirken har navnt efter fattigforsørgeren Sankt Stefanus, der som det fortælles i Bibelen blev stenet til døde og derfor martyr.
Stefansgade hed tidligere Havremarksvej, som førte gennem området mellem Nørrebrogade og Jagtvej, der kaldtes Havremarken. I dage findes navnet stadig i Havremarkens Skole i >Husumgade.
På et tidspunkt havde man kaldt den nuværende Bragesgade for Stephansgade – sikkert lige efter kirkens indvielse i 1874.
Stefansgade førte fra Nørrebrogade til Nørrebro Station, der eksisterede fra 1886 til 1930. Den er nærmere omtalt under Nordbanegade.
I Stefansgade grundlagdes i 1895 Bryggeriet Stefan, der senere under navnet Hafnia producerede bl.a. hvidtøl.
Stefansgade 35, mellem Husumgade og Bjelkes Allé, er opført i 1899. Ejendommen er forsynet med franskinspirerede hjørnetårne og tegnet af P. E. O. Petersen, der også var bygherre.