Fu fatto erigere a partire dal 1571 da Franco Lercari, facoltoso banchiere, che occupò la carica di governatore della Repubblica Genovese negli anni settanta del Cinquecento e fu committente anche di Villa Lercari a Sampierdarena e della Cappella Lercari nell'abside della Cattedrale di San Lorenzo. Nel 1586 Franco Lercari lasciò, con l'obbligo di assumere anche il cognome Lercari, tutto il suo patrimonio a Francesco Maria Imperiali di Francavilla. L'ultima discendente degli Imperiali Lercari fu Maria Luigia che sposando il marchese modenese Lodovico Coccapani, in seguito Coccapani Imperiali, portò il palazzo in dote. I discendenti Ercole e Lodovico Coccapani Imperiali nel 1845 lo vendettero al banchiere Bartolomeo Parodi, la cui famiglia ne è ancora proprietaria.
Il palazzo, di cui non si conosce il progettista, si differenzia dagli edifici della Strada Nuova. La parte inferiore della facciata è decorata a bugnato a punta di diamante, mentre i piani superiori risultavano all'origine alleggeriti da una serie di logge aperte, poi chiuse da vetrate e murate all'inizio dell'Ottocento, come si vede dalle incisioni di Rubens nell'edizione dei Palazzi di Genova del 1652. Sempre nella facciata ha particolare rilievo il portale retto da due telamoni con nasi mozzi, opera di Taddeo Carlone, che qui rievoca l'atroce leggenda di Megollo Lercari, antenato del committente, vendicatosi dei suoi nemici mutilandoli di nasi e orecchie.
Nella volta del salone del secondo piano nobile si trova un celebre capolavoro del manierismo genovese: l'affresco di Luca Cambiaso che raffigura L'impresa di Megollo Lercari della costruzione del fondaco dei genovesi a Trebisonda, ossia le costruzioni necessarie per condurre i commerci nella colonia genovese sul mar Nero.
