Før 1920: Steinstrasse efter købmand B. Stein.

Tidl. dansk navn: Kiedelsmedgaden.

Stein var ejer af flere ejendomme i området. Burde ikke have været oversat til dansk i 1920.

Kedelsmedgade var foreslået, men det blev afvist af beboerne.

Kilde: Alsiske stednavne

Trappefortovet er anlagt i 1926. 

Her en anden udlægning:

I 1920 opstod der stor strid om, hvorvidt Steinstrasse skulle omdøbes til Steinsgade eller Stengade. Det påstås, at den er opkaldt efter købmand Stein, hvis købmandsgård endnu ligger mellem Rådshustorvet og Bjerggade. Og Bjerggades gamle navn er Bag Møddingen eller Am Mistphal. Ville man hædre købmanden, havde det været naturligt at omdøbe BAg Møddingen. I tysk tid hed gaden ikke Steins-Strasse, men Steinstrasse, altså uden ejefalds-s, og den dansktalende befolkning sagde Stengade, for såvidt den ikke brugte det ældre navn Kedelsmedbjerget. 

Syd for grænsen findes der ikke så få gader kaldet Steinstrasse, og i Danmark forekommer gadenavnet Stengade ikke mindre end femeten gange. Er det ikke nærliggende, at gaden har fået sit navn efter brolægningen? Så meget mere, som den var en hovedtrafikåre efter pontonbroens etablering og formentlig har været en af de første gader, der blev brolagt.

Kilde: Robert Huhle, Sønderborg billeder fra svunden tid.