Sama ulica Gajowa powstała na śladzie dawnej odnogi tak zwanej szosy Strzelińskiej, biegnącej w miejscu dzisiejszej ulicy Hubskiej, wiodącej do wsi Gaj, położonej nieco dalej na południe przy nieistniejącym współcześnie odcinku ulicy Gajowej, między ulicą Kamienną a ulicą Śliczną. Wieś ta została włączona do miasta w 1904 r..
W 1864 r. wytyczono ulicę Suchą, zgodnie z opracowanym w 1856 r. pierwszym planem regulacyjnym przedmieść. Już u schyłku XIX wieku powstały przy ulicy Gajowej pierwsze ogrody działkowe. Znajduje się tu do dziś zachowany ogród założony przed 1912 r.. Natomiast ulicę Kamienną, na odcinku łączącym się z ulicą Gajową wytyczono od 1915 r. według skorygowanego projektu urbanistycznego przedmieścia południowego z 1895 r.. Po pierwszej wojnie światowej wytyczono natomiast dzisiejszą ulicę Przestrzenną. Ówcześnie była to ulica Goethego i obejmowała także ulicę Wielką, stanowiąc całość od placu Ludwika Hirszfelda do ulicy Hubskiej. Już wówczas przy skrzyżowaniu z ulicą Gajową wytyczono plac, który również otrzymał imię poety (Geotheplatz). Współcześnie plac ten nie posiada odrębnej nazwy, a w jego obszarze zachowano urządzony teren zieleni – Zieleniec przy ul. Przestrzennej.