Gaden er opkaldt efter den svenske statsminister, Olof Palme (1927-1986), efter at han blev myrdet i 1986. Dermed falder navnet ind i kvarteret med gader opkaldt efter svenske byer, og den nærliggende Dag Hammerskjölds Allé, opkaldt efter den svenske FN-generalsekretær.
Tidligere hed gaden Skjoldsgade. Forklaringen på dette navn er uvis.
På Olof Palmes Gade ligger dels en række fornemme etageejendomme, dels to villaer, der sammen med yderligere to på Hjalmar Brantings Plads, føjer sig til villabebyggelsen i kanten af Holmens Kirkegård.
I nr. 8 (billedet herover) boede redaktøren og forfatteren Edvard Brandes (1847-1931). Huset er opført omkring 1902 efter tegninger af arkitekten Eugen Jørgensen (1858-1910).
Det har på bagsiden en atelierbygning, hvor Edvard Brandes hustru, billedhuggeren Elise Brandes (1873-1918) arbejdede med sine portrætbuster. I dag er villaen i brug som mødefaciliteter og har fået en moderne tilbygning, kaldet Edvard Brandes Palæ.
Ved bygningen står en skulptur (herunder) udført af Henri Marie Jean André de Laborde de Monpezat (1934-2018).
I Olof Palmes Gade 10 (herunder) boede fra omkring 1910 Mads Rasmussen, der direktør for konservesfabrikken Beauvais på Lyngbyvej. Han var også stifter af Faaborg Museum, og i huset kom nogle af tidens kunstnere.
