L’antico palazzo fu costruito dai Colonna sulle strutture dell’emiciclo superiore del Santuario della Fortuna Primigenia intorno al 1050, epoca in cui la famiglia si insediò a Palestrina.
L’edificio subì una prima distruzione nel 1298, quando Palestrina, dopo un assedio durato quasi un anno, fu rasa al suolo per ordine di Bonifacio VIII, il quale aveva ingiunto la confisca dei beni ai Colonna che avevano tentato di contrastarne l’elezione. Dopo la sconfitta i Colonna firmarono un documento di sottomissione al papa nel quale si descrive il palazzo e i danni da questo subiti: se ne deduce che a quell’epoca la struttura aveva due torri ai lati e che svolgeva quindi la funzione di fortezza militare, in una posizione a dominio della città e della campagna sottostante.
La città fu presto ricostruita, e con essa la residenza dei principi, ma subì una seconda rovinosa devastazione nel 1437, ad opera di Eugenio IV che, entrato in discordia con i Colonna, diede ordine al cardinale Vitelleschi, capo delle truppe pontificie, di muovere su Palestrina.
Il successore di Eugenio IV restituì ai principi prenestini il feudo e acconsentì alla ricostruzione della città e del palazzo: venne chiuso il colonnato e l’edificio diventò a due piani. Sembra che intorno al 1450 abbia soggiornato nel palazzo Leon Battista Alberti, il famoso umanista e architetto.
Tra il 1450 e il 1500 Francesco Colonna lo ricostruì nuovamente, aggiungendo al centro della scalinata semicircolare il pozzo ottagonale sormontato da due colonne; fu realizzato il portale, del 1498, strettamente connesso con quello del contemporaneo palazzo di S. Croce a Roma; le finestre furono allargate e sistemate in modo simmetrico.
Il palazzo si distingue dalle altre costruzioni romane erette su antichi monumenti per la scelta consapevole della sua forma, che rappresenta una sintesi voluta tra antico e moderno, un felice prodotto della progettazione rinascimentale che influenzò addirittura il Bramante, il quale ne ripropose l’aspetto nel Belvedere del Vaticano.
Maurizio Calvesi ha identificato l’architetto del palazzo proprio in Francesco Colonna, l’autore dell’Hypnerotomachia Poliphili (Battaglia d’amore in sogno di Polifilo), famoso libro stampato nel 1499, ornato da incisioni attribuite tra gli altri a Mantegna, a Giovanni Bellini e a Raffaello, e considerato il libro tipograficamente più bello del Rinascimento e uno dei più significativi per una documentazione di storia dell’architettura e delle dottrine delle arti figurative.
Nel 1630 i Colonna vendettero la città e il palazzo a Carlo Barberini, fratello di Urbano VIII, per 775.000 scudi. Dieci anni più tardi l’edificio fu ricostruito nella sua forma attuale da Taddeo Barberini; nello stesso anno il cardinale Francesco, fratello di Taddeo, vi collocò il celeberrimo mosaico del Nilo.
Pochi anni dopo fu costruita da Francesco Contini l’adiacente chiesa di S. Rosalia, commissionata da Maffeo Barberini in ringraziamento per la salvezza della città da un’epidemia di peste; qui fu per lungo tempo conservata la Pietà Barberini attribuita a Michelangelo, ora a Firenze nella Galleria dell’Accademia.