Gaden er opkaldt efter Johann Friedrich Struensee (1737-1772) og anlagt omkring 1890.
I starten hed den Skolegade, men navnet blev i 1906 ændret til det nuværende. Ændringen skyldtes nok, at der også var en Skolegade i Valby, som var blevet indlemmet i Københavns Kommune nogle år før.
Navnet Skolegade har ingen sammenhæng med, at Metropolitanskolen omkring 1940 flyttede herud fra Fiolstræde i den indre by.
Den vestlige del af Struenseegade blev i 1920’erne bebygget med ejendomme opført af Københavns Kommune.