Il palazzo fu costruito tra il 1586 e il 1589 per Ottavio Imperiale, con la spesa ragguardevole di 50.000 scudi d'oro. L’aristocratico e letterato genovese Giulio Pallavicini ricorda l'inizio dei lavori come uno degli avvenimenti più notevoli dell'anno. 

Passato in mano alla famiglia Sauli nel primo Seicento, l’edificio si arricchì con una serie di splendide decorazioni: una maestosa statua di Ercole vincitore con i Pomi delle Esperidi commissionata allo scultore genovese Filippo Parodi, un ciclo di affreschi di Domenico Piola nella galleria che si affaccia sul cortile interno, detta “la galleria dei Pianeti” e l’allestimento di una ricchissima quadreria che comprese alcune delle opere più straordinarie del Barocco italiano, realizzate da artisti del calibro di Orazio Gentileschi.

A seguito della morte di Lorenzo Sauli, nel 1684, la proprietà del palazzo passò alla famiglia De Mari che si occupò di terminare la decorazione del secondo piano, chiamando ad affrescare le restanti volte il savonese Bartolomeo Guidobono e il bolognese Giacomo Antonio Boni. 

Il pianterreno e il primo piano del palazzo ospitano da molti decenni un grande magazzino, dove è ancora visibile la monumentale statua del Parodi, mentre l’appartamento affrescato al secondo piano è accessibile solo in particolari occasioni. Annoverato ancor prima del termine della costruzione tra i palazzi dei Rolli, fu anche citato da Rubens nel suo repertorio di rilievi delle dimore genovesi.

Sul frontone del portale è cresciuto spontaneamente da tempo immemorabile un melograno, da cui ha origine il nome con cui l’edificio è comunemente conosciuto a Genova: Palazzo del Melograno.