Il Palazzo sorge su quella che in epoca romana era chiamata Porta Decumana. A partire dal I secolo la porta venne trasformata in una fortificazione di modeste dimensioni, pur mantenendo l'originaria funzione di varco. È dal XIV secolo in poi che il ramo Savoia-Acaja trasforma l'originaria porta in castello con una serie di interventi che conferirono all'edificio la forma quadrata con corte, portico e quattro torri cilindriche.

Con l'estinzione del ramo d'Acaja, il castello diventò una residenza per gli ospiti. Nel 1637 la reggente del duca Carlo Emanuele II di Savoia, Maria Cristina di Borbone-Francia, lo elesse come sua residenza personale e avviò una serie di interventi per modificare la struttura e ammodernare gli appartamenti. Ma è a un'altra donna di casa Savoia, Maria Giovanna Battista di Savoia-Nemours (reggente di Vittorio Amedeo II di Savoia) che si deve l'aspetto attuale del palazzo e parte del nome, essendo stato sede delle reggenze di due "Madame Reali".

Fu tolto l'antico ponte levatoio e furono chiamati ai lavori di restauro Carlo ed Amedeo di Castellamonte, assieme al pittore Guglielmo Caccia. Filippo Juvarra progettò un magnifico palazzo barocco in pietra bianca. I lavori però non furono mai conclusi.