Charlemagne Émile de Maupas (1818-1888), sénateur et préfet des Bouches du Rhône de 1860 à 1866, s’estimant mal logé dans l’hôtel Roux de Corse actuellement Lycée Montgrand, décida la construction d’un monument somptueux digne de son rang. Il en confie la réalisation à l’architecte départemental Auguste Martin (1818-1877) et fait approuver le projet et son financement par le Conseil Général réuni en session extraordinaire le 7 janvier 1861.
En novembre 1861 les terrains étaient achetés et les immeubles rasés. L’emplacement choisi se trouvant sur le tracé des anciens fossés et remparts réalisés en 1669 par Nicolas Arnoul sur ordre de Louis XIV, il fallut effectuer des fondations spéciales à cause de l’instabilité du sol. Cet inconvénient se manifesta également lors de la réalisation du parc de stationnement souterrain de la Préfecture ; en effet il fallut interrompre les travaux de creusement pour réaliser des injections de béton car la façade principale du bâtiment de la Préfecture fut déstabilisée.
La première pierre fut posée le 18 septembre 1862 et les travaux de construction commencèrent à un rythme soutenu. Par suite de mésentente avec le préfet Maupas et à cause des dépassements des devis initiaux, l’architecte Martin démissionna le 8 novembre 1864 et fut remplacé par François-Joseph Nolau (1804-1883) architecte parisien qui avait une grande expérience pour les décors intérieurs.
Les travaux furent terminés fin 1866. Le préfet Maupas prit possession de son palais préfectoral en décembre 1866, mais ayant trop présumé de son crédit, il fut relevé de ses fonctions par un décret de l’Empereur fin décembre 1866. Cela ne l’empêcha pas de procéder à l’inauguration qui eut lieu le 1 janvier 1867.