Il Palazzo 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 autocelebrazione, 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 il nostro edificio, 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.