Opkaldt efter Stephan Tetens, som levede fra 1773 til 1855. Biskop, født i Horsens. Faderen Peter Tetens var rektor i Horsens. Gaden hed tidligere Allegyden og Pistolstræde.
Om Stefansgade skriver Aage Simonsen i “Gamle gader i Horsens”:
Da de første Bygninger i 1840’erne rejste sig i Stefansgade, udgjorde denne kun en ganske smal Passage mellem Allégade og Houmannsgade. Senere blev den udvidet baade i Bredden og Længden. Gaden har haft flere Benævnelser: Allégyde, Pistolstræde og fra omkring 1860 Stefansgade.
I 1871 blev der stiftet en Byggeforening i Horsens med Navnet “Arbejdernes Byggeforening”, den første af sin Art i Byen. Den havde til Formaal at opføre gode, sunde Boliger, som paa billige Vilkaar skulde udlejes til Foreningens medlemmer. Kapitalen, hvorfor Bygningerne opførtes, blev skaffet tilveje dels igennem en Aktietegning og dels igennem en Sparekasse. Foreningens Formand var Købmand Carl Joh. Pødenphant.
Foreningen købte en Byggegrund i Stefansgade og opførte 1875 5 toetages Huse med Lejlighed til 18 Familier. Dette store Foretagende samt Bryggeriets Ombygning og Udvidelse i 1879 har i særlig Grad formaast at præge den ældste Del af Stefansgade.