Den ganske korte gade er opkaldt efter en by i Norge.
Gaden hed tidligere Frederikshaldsgade, og skulle have været en del af en gennemgående indfaldsvej til Østerbro og via Livjægergade have skabt forbindelse til Classensgade.
Som en pompøs indgang til Østerbro, når man kommer fra Langeliniebroen, ligger de to ejendomme Gefion og Gylfe. De er de eneste bygninger i Mandalsgade.
Bygningerne er tegnet af arkitekten Phillip Smith (1855-1938), og opført omkring 1902. Han har også tegnet den store ejendom ved Frithjof Nansens Plads. Ejendommen er fredet.
Gefion er en af oldtidens gudinder. Sagnet fortæller, at svenskernes konge, Gylfe, som morgengave til Gefion, gav hende så meget land, som fire okser kunne pløje på én dag og én nat. Gefion skabte sine fire sønner om til okser, og de pløjede så meget land ud af Sverige, at det blev til Sjælland. ”Hullet ” i Sverige blev til søen Väneren.
Sagnet har også været inspiration for udførelsen af Gefionspringvandet ved Churchillparken. De to sagnfigurer har også givet navne til gader i området. Frithjof Nansens Plads hed tidligere Gylfesgade og en lille sidegade til den hedder Gefionsgade.