L'histoire du Palais remonte à l'Exposition internationale de 1931. Sa vocation première fut d’être un musée des colonies, devant représenter l’histoire de la conquête coloniale, des territoires colonisés ainsi que son incidence sur les arts.

Après l’exposition coloniale, le palais changea d’attributions au gré des évolutions de l’histoire : musée permanent des Colonies jusqu’en 1935, puis musée de la France d’Outre-mer jusqu’à la fin des années 1950, il accueille en 1961 le musée des Arts africains et océaniens qui deviendra le musée national des Arts d’Afrique et d’Océanie en 1990.
Avec la création du musée du Quai Branly – Arts et civilisations d’Afrique, d’Asie, d’Océanie et des Amériques –, et la fermeture du MAAO en 2003, seul l’Aquarium tropical et les salles historiques du rez-de-chaussée restent ouverts au public.

Depuis 2007, le bâtiment abrite la Cité nationale de l’histoire de l’immigration, après une période de travaux de réaménagement, conduits par Patrick Bouchain et Loïc Julienne de l’atelier Construire.