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.