Fu costruito tra il 1559 e il 1565 da Giovan Battista Castello detto il "Bergamasco" e da Bernardino Cantone per volere di Nicolosio Lomellino, esponente di una famiglia in piena ascesa economica e politica. Imparentato con il principe Andrea Doria, accumulò ingenti capitali nella prima metà del Cinquecento quale concessionario della redditizia pesca del corallo nell'isola tunisina di Tabarca. Agli inizi del Seicento la proprietà passò alla famiglia Centurione che effettuò una ristrutturazione interna, poi ai Pallavicini, ai Raggi ed infine ad Andrea Podestà, più volte sindaco di Genova tra il 1866 e il 1895.
La facciata, su progetto del Bergamasco, è movimentata da una ricca decorazione a stucco, con erme femminili alate, a sorreggere la cornice marcapiano del pianterreno; nastri e drappi a reggere, al primo piano, trofei d'armi; ghirlande e mascheroni a coronamento delle finestre, con figure classiche entro medaglioni ovali, al secondo. La decorazione a stucco all'antica, applicata per la prima volta in epoca moderna da Raffaello nelle Logge vaticane e precocemente importata a Genova dal suo allievo Perin del Vaga nella decorazione della villa del Principe, si dispiega qui per la prima volta su vasta scala coprendo l'intero prospetto. La sua esecuzione è attribuita all’urbinate Marcello Sparzo.
L'opera pittorica più antica del palazzo è il ciclo di affreschi realizzati nel 1623-1624 dal pittore genovese Bernardo Strozzi e successivamente occultati a causa di una lite con il committente Luigi Centurione, che aveva acquistato il palazzo nel 1609 da Nicolosio Lomellino. I documenti, ancor oggi esistenti, relativi alla lite intercorsa tra l'artista e Centurione (1625), confermano l'intervento del pittore in tre stanze del primo piano nobile, i cui affreschi furono celati dai successivi interventi con uno spesso strato di intonaco e una controsoffittatura nel salone centrale. Rimossa nel 2002, al di sotto di essa è ricomparsa, con i suoi colori smaglianti, l'Allegoria della Fede.
Al secondo piano nobile è invece conservata la decorazione a tema mitologico voluta agli inizi del XVIII secolo dai Pallavicino. È costituita da capolavori dei maggiori esponenti del tardo barocco genovese. In due salotti del piano nobile il bolognese Giacomo Antonio Boni affrescò Giove e la capra Amaltea e Domenico Parodi Bacco regge la corona Arianna. Di Lorenzo De Ferrari è la decorazione a stucco e ad affresco con figure di divinità sulla volta della galleria. Il salone, decorato da Tommaso Aldrovandini, custodisce cinque celebri tele con Storie di Diana eseguite da Marcantonio Franceschini, pittore bolognese chiamato a Genova per la decorazione del salone del Maggior Consiglio di palazzo Ducale.
Sono visitabili gli spazi del Cortile, dell'Appartamento Strozzi, della Sala del Calvalier Tempestae del Giardino.
