Die Straße verläuft heute unter dieser Bezeichnung von der Wilhelmshöher Allee bis zum Stadthallengarten. Ursprünglich hieß der Abschnitt zwischen der Wilhelmshöher Allee und der Kaiserstraße (Goethestraße) Zedlitzstraße und war damit dem Politiker und Beamten Robert Graf von Zedlitz-Trützschler gewidmet, der von 1898 bis 1903 Oberpräsident der preußischen Provinz Hessen-Nassau war.

An der Kaiserstraße traf die Zedlitzstraße auch auf die Aschrottstraße. Deren Namen tilgte man im Nationalsozialismus und setzte die Zedlitzstraße bis zum Stadthallengarten fort. Im Rahmen der Umbenennungen des Jahres 1947 bekam die gersamte Zedltizstraße die Bezeichnung Freiherr-vom Stein-Straße, die an Heinrich Friedrich Karl Reichsfreiherr von und zum Stein (1757-1831 erinnert, einen der bedeutenden Pollitker im Zusammenhang der preußischen, der Stein-Hardenbergschen,-Reformen zu Beginn des 19. Jahrhunderts.