L'antico palazzo fu costruito dai Colonna sulle strutture dell'emiciclo superiore del Santuario ellenistico della Fortuna Primigenia intorno al 1050. L'edificio subì una prima distruzione nel 1298, quando Palestrina fu rasa al suolo, per ordine di Bonifacio VIII, il quale aveva ingiunto la confisca dei beni ai Colonna che avevano tentato di invalidarne l'elezione. La città venne ricostruita, ma subì un'ulteriore devastazione nel 1437 ad opera di Eugenio IV.
Il successore di Eugenio IV restituì ai Colonna il feudo e acconsentì la ricostruzione della città: venne chiuso il colonnato e l'edificio diventò a due piani.
Tra il 1450 e il 1500 Francesco Colonna lo ricostruì nuovamente, aggiungendo il pozzo ottagonale fiancheggiato da due colonne, fu realizzato il portale e le finestre furono sistemate in modo simmetrico.
Nel 1630 i Colonna vendettero la città e il palazzo a Carlo Barberini. Nel 1640 l'edificio fu ricostruito nella sua forma attuale da Taddeo Barberini e vi fu collocato il celeberrimo mosaico del Nilo, rinvenuto tra la fine del XVI e i primi anni del XVII. Maffeo, suo figlio fece altre aggiunte ed eresse la chiesa di S. Rosalia e il ninfeo situato nel retro del corpo principale. Anche una parte della decorazione interna, gli affreschi tradizionalmente attribuiti alla scuola degli Zuccari è dovuta ai Barberini.
