Išplanuota XIX a. pradžioje Vilhelštato rajone. Iš pradžių vadinta Grosse Sandstrasse (Didžioji Smėlio g.), nes traktuota kaip to vardo gatvės tąsa. XX a. pradžioje jau vadinama Schutzen Strasse (Šaulių g.), mat šalia jos stovėjo šaulių organizacijos namas (buv. Karininkų namai dab. Klaipėdos koncertų salė), buvo šaudykla. Šis pavadinimas egzistavo iki tarybinių metų, kai ją pervadino į Raudonosios Armijos, o vėliau – į Tarybinės Armijos g. Be to, tuo pat vardu pavadinta ir gatvė iki Priestoties g., kuri anksčiau vadinta Vynerio promenada, o po 1939 m. aneksijos – Tannenberg Strasse.