Ulica powstała pod koniec XIX wieku. Jej najstarszy odcinek biegł od ul. Wielkiej na południe do nieistnijącej dziś drogi zwanej Kräuterweg. Przedłużenie dalej na południe aż do ul. Sztabowej nastąpiło w pierwszych latach XX wieku. Mniej więcej w tym samym czasie powstała zabudowa ulicy. Patronem został Johannes Gensfleisch zum Gutenberg (ok. 1396-1468), złotnik i drukarz, wynalazca ruchomej czcionki.

W czasie II wojny światowej cała zabudowa ulicy została zrównana z ziemią. Po wojnie wprowadzono obecną nazwę w pewnym stopniu nazwiązującą do przedwojennej. W kolejnych latach w miejscu przedwojennych domów wzniesiono nowe bloki z wielkiej płyty.

Ulica zaczęła powstawać w 1863 r., kiedy urzędnik miejski Nowak przeznaczył część swej parceli przy ul. Piłsudskiego pod nową ulicę. Już dwa lata później otrzymała nazwę Neudorfstr. gdyż prowadziła do dawnej Nowej Wsi należącej do komadnorii joanitów. Stopniowo kamienice czynszowe zaczęły wypierać dawną zabudowę podmiejską i wiejską. W latach 1875-1911 przy południowym odcinku ulicy wzniesiono budynki szpitala Wenzel-Hancke (dziś Akademia Ekonomiczna). Plany urbanistyczne z końca XIX w. przewidywały przedłużenie ulicy do al. Wiśniowej. Niestety zrealizowano tylko krótki odcinek tuż przy dawnym Szpitalu Żydowskim (dziś Szpital Kolejowy), który nigdy nie został połączony z główną ulicą.

W czasie wojny wszystkie kamienice zostały zburzone, ocalały jedynie zabudowania dawnego szpitala. Obecna nazwa do 20 III 1972 r. odnosiła się do "głównego" odcinka oraz fragmentu przy al.Wiśniowej. Od tego czasu ten ostatni zaliczany jest do al. Wiśniowej.

Pierwsze plany wytyczenia nowej ulicy pojawiły się w 1895 r. w projekcie urbanistycznym Przedmieścia Południowego. Od początku napotykano spore trudności w realizacji tych planów, w związku z niechęcią właścicieli do oddawania terenu, przez które miała przebiegać ulica. Pierwszy, dwupasmowy odcinek od pl. Powstańców Śląskich do ul. Drukarskiej powstał ok. 1900 r. Drugi odcinek, od ul. Ślężnej do ul. Bardzkiej powstawał od 1915 r. Obie części łączyła Kräuterweg (do 1900 r. pod nazwą Am Neudorfer Weg) biegnąca od ul. Drukarskiej do ul. Ślężnej tuż przy ogrodzeniu obecnej Akademii Ekonomicznej.
Właściwą ulicę nazwano Steinstr. dla upamiętnienia pruskiego ministra, barona Karla von und zum Stein.

W 1945 r. zabudowa ulicy została niemal doszczętnie zniszczona. Wtedy też zmieniono nazwę na ul. Kamienną, tłumacząc na polski nazwisko niemieckiego patrona tej ulicy.