Die Straße ist seit 1869 nach dem Feldherrn Wallenstein benannt und hieß ursprünglich Untere Quergasse, teilweise auch Gärtnergasse. Die um 1863 genannte Dammstraße entspricht der heutigen Wallensteinstraße.
Seit der Teilung des Bezirkes im Jahre 1900 liegt die Straße im 20. Bezirk, davor gehörte das Gebiet zum 2. Bezirk, der als Werd (= Insel im Strom) bezeichnet wurde. Vom Gebiet des heutigen Wallensteinplatzes gibt es im Bezirksmuseum Brigittenau eine Zeichnung aus dem 17. Jahrhundert. Damals war dort die Kreuzung der Jägerstraße mit der Unteren Quergasse bzw. der damaligen Dammstraße. Die Zeichnung zeigt einige einfache, verstreute Hütten mit der Spitze des Stephansdoms in der Ferne.
Die stärkere Besiedelung der Brigittenau führte zur Neustrukturierung der Straßen und dem Verschwinden des alten Dammes zum Augarten hin, der Augartenpalais und barocke Gartenanlage vor Hochwasser schützte. Die Stadtentwicklung ist am Wallensteinplatz gut erkennbar. Im Westen liegen einfache, aus der Gründerzeit stammende Zinshäuser für Arbeiter, während der Platz an den anderen Seiten von Nobelmiethäusern aus der Zeit um 1900 dominiert wird. Am Wallensteinplatz hielt bereits Anfang der 1840er Jahre die Brigittenauer Eisenbahn, eine Pferdebahn, Vorläuferin der Wiener Straßenbahn, die vom Donaukanal (beim Rotenturmtor) über Obere Donaustraße, Gaußplatz und Jägerstraße zum Vergnügungsetablissement Kolosseum in der Zrinyigasse 15 führte. Um 1872 war die Straße in der Umgebung des Nordwestbahnhofs noch in der Entwicklungsphase. Es hieß, die Wallensteinstraße sei noch unreguliert, unbeleuchtet und kaum bebaut. Sie reichte damals allerdings bis zum Tabor. Erst 1876 erfolgte eine Aufteilung in Rauscherstraße und (untere) Nordwestbahnstraße.
(Quelle: straßenbahnjournal.at)