A parte mais antiga do palácio data do século XIII e, segundo a tradição, hospedou Dante em sua visita a Roma. A primeira menção documental menciona que, na época, moravam ali os cardeaisGiovanni e Giacomo Colonna. Foi ali também que viveu o cardeal Oddone Colonna, eleito depois papa como Martinho V (r. 1417–1431).
Com a morte dele, o palácio foi saqueado num dos muitos conflitos entre as famílias de Roma e a propriedade passou para a família Della Rovere. Os Colonna recuperaram o palácio quando Marcantonio I Colonna casou-se com Lucrezia Gara Franciotti Della Rovere, uma sobrinha do papa Júlio II. A aliança dos Colonna com os Habsburgos provavelmente foi o que manteve o palácio a salvo durante o saque de Roma em 1527.
Começando com Filippo Colonna (1578–1639), muitas mudanças foram realizadas e criaram um complexo unificado à volta de um jardim central. Diversos arquitetos, incluindo Girolamo Rainaldi e Paolo Marucelli, trabalharam em projetos específicos. Apenas nos séculos XVII e XVIII é que as fachadas foram completadas, uma de frente para a Piazza SS. Apostoli e a outra, para a Via della Pilotta. Muito do projeto foi completado por Antonio del Grande (incluindo a galeria principal) e Girolamo Fontana (decoração da galeria). No século XVIII, a longa fachada baixa de frente para a Piazza SS. Apostoli, projetada por Nicola Michetti com adições posteriores de Paolo Posi, com cantos mais altos foi construída lembrando estruturas mais antigas parecidas com fortificações.
