Palazzo Lomellino venne edificato per volontà di Nicolosio Lomellino tra il 1563 e il 1569 circa, su progetto dell'architetto lombardo Giovanni Battista Castello detto il Bergamasco. Nel 1550, per rispondere all'esigenza di alcune famiglie aristocratiche genovesi, venne 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 auto celebrazione, fece a gara nel commissionare eleganti dimore ai più importanti architetti del tempo, che poterono qui sperimentare soluzioni innovative e aggiornate.

Il lotto su cui sorge Palazzo Lomellino, suolo pubblico già di Luca Grimaldi, era stato in un primo tempo acquistato dalla famiglia Gentile nel 1559, in occasione della prima asta pubblica dei terreni; passò quindi ai Lomellino nel 1563, che iniziarono subito la campagna dei lavori. Il committente Nicolosio Lomellino aveva accumulato un'ingente fortuna investendo, insieme al fratello Francesco, nella redditizia pesca del corallo nell'isola tunisina di Tabarca. Secondo l'ultima ricostruzione di Pesenti il Palazzo venne acquistato nel dicembre del 1609 da Luigi Centurione, mentre il passaggio ai Pallavicini è stato datato correttamente da chi scrive al 1711, grazie al ritrovamento di nuove carte d'archivio (Manzitti, Priarone c.d.s.). Dopo una breve parentesi di proprietà Raggi, nel 1865 il barone Andrea Podestà, figura di spicco della Genova del tempo e per ben tre volte sindaco della città, acquisì l'immobile, che per discendenza diretta è pervenuto agli attuali proprietari.

All' interno di Palazzo Lomellino si trova il ciclo di affreschi di Bernardo Strozzi, realizzati nel 1623-1624. 

Oggi è possibile ammirare, con i suoi colori smaglianti, l' Allegoria della Fede raffigurante una scialuppa a remi dalla quale una donna,  (la fede cristiana) è aiutata a sbarcare sulla terraferma, per portare la fede agli indigeni del Nuovo Mondo. Nelle altre due stanze, in condizioni più precarie, sono stati ritrovati affreschi sull'Astrologia e frammenti con la Navigazione e Tritoni. 

Al secondo piano si trovano invece affreschi dei più importanti esponenti del tardo barocco genovese: 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, con decorazioni di Tommaso Aldrovandini, custodisce cinque celebri tele con Storie di Diana eseguite da Marcantonio Franceschini.