Nel 1550, per rispondere all'esigenza di alcune famiglie aristocratiche genovesi, fu disegnato un nuovo asse viario - l'odierna Via Garibaldi - per congiungere il centro medievale e le aree a levante, dando vita così ad un nuovo quartiere di magnificenza. L'antica "Strada Nuova dei Palazzi" di fatto divenne una zona elitaria, dove l'aristocrazia della città, appagando il proprio desiderio di autocelebrazione, fece a gara nel commissionare eleganti dimore ai più importanti architetti del tempo, che poterono qui sperimentare soluzioni innovative e aggiornate. Palazzo Lomellino fu eretto a partire dal 1563 per Nicolosio Lomellino da Gaetano Cantoni, su progetto di Giovanni Battista Castello, detto il Bergamasco, con decorazioni a stucco di Marcello Sparzo.
Nel 1609 il palazzo fu ceduto alla famiglia Centurione. Nel 1711 la proprietà passò alla famiglia Pallavicini, cui si debbono gli importanti lavori di ristrutturazione, specialmente al primo e secondo piano nobile, nel giardino e nei ninfei. Nel 1865, l’edificio fu acquistato dall’allora sindaco Andrea Podestà, figura di politico, urbanista e imprenditore nella Genova del XIX secolo.
I documenti, ancor oggi esistenti, relativi alla lite intercorsa tra il pittore genovese Bernardo Strozzi e il committente Luigi Centurione (1625), confermano l’intervento del pittore in tre stanze del primo piano nobile, con un ciclo di affreschi realizzati nel 1623-1624. Gli 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. Nelle altre due stanze, in condizioni più precarie, sono stati rinvenuti l’Astrologia e frammenti con la Navigazione e Tritoni.
