Park Andersa to niegdysiejszy teren dużej nekropolii wrocławskiej, w skład której wchodziły wymienione w obiekcie cztery cmentarze

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.