Sommige geschiedkundigen aarzelen niet deze straat te bestempelen als de oudste van Brussel! De benaming komt waarschijnlijk
van het steen De Gulden Poirte dat zich bevond tegenover de vroegere Melkmarkt achter de Beurs,
vandaag de Taborastraat
maar vroeger ook wel Kleine Steenstraete genoemd. Anderen menen dat de naam mogelijk verwijst naar haar vroegere
functie van opslagplaats van het bouwmateriaal voor de bouw van het Stadhuis. In ieder geval wordt de straat reeds als dusdanig
vermeld in de tweede helft van de 13de eeuw en maakte ze deel uit van de handelsweg die van het Groot Eiland naar de
Koudenberg liep.
De Spiegelbrug verbond de Steenstraat met het Sint-Gorikseiland, nu eindigt ze aan de
Anspachlaan.
In 1355 werd in deze straat de Stadswaghe geïnstalleerd, die verdween toen in 1861-1862 de
Zuidstraat
in noordelijke richting verlengd werd. Verderop, ter hoogte van de nummers 15-21, stond het godshuis van de kramersgilde,
wederopgebouwd in 1781. Ingevolge de Zennesanering en het aanpassen van de N-Z-rooilijn verdwenen rond 1867-1880 de voormalige
Steengang (nabij het huidige nr. 10), de Minderbroedersstraat (nr. 20-22), de Korte Steenstraat (nr. 26-28) evenals de
Appelbomengang.
Sinds 2007 wordt ze ook Lucky Lukestraat genoemd, naar de stripfiguur van Morris.