Questo edificio già a partire dal 1311 è indicato come il palacium ubi ius redditur, cioè dove si amministra la giustizia, funzione mantenuta fino ad oggi in una straordinaria continuità d'uso.
All'originario edificio, probabilmente eretto nella seconda metà del Duecento, sono riconducibili gli archetti pensili ritornati alla luce dopo la rimozione delle pesanti intonacature, che avevano obliterato le strutture anteriori e la ricca decorazione dipinta sulle facciate.
L'originaria fase medievale conobbe un primo rifacimento nel 1462, quando Guglielmo Casatroia, a nome del marchese Giovanni I, commissionò al maestro Giorgio Molinaro de Plebe la ristrutturazione del palazzo. A questi interventi appartiene la lunetta in Pietra di Finale con le Quattro Virtù Cardinali, datata 1462, e la sottostante immagine del Giudice togato, con la scritta sul cartiglio Nichil utille nixi sit honestum (Niente è utile che non sia onesto).
Il palazzo medievale si presentava aperto in un loggiato a pianterreno e finestre architravate con colonnine centrali, ancora visibili in facciata.
Del tutto eccezionale è la ricca decorazione dipinta tra la fine del XV e gli inizi del XVI secolo con un finto bugnato a piramide tronca in verde e rosso, percorsa da una serie di fasci con una girale con motti che alludono alla forza e al diritto, fogliami e putti. 
La facciata è stata oggetto di un complesso restauro nel 2011. 
Sul lato sinistro, visibile dalla strada che porta a Castel San Giovanni, si conserva il loggiato con un fregio in terracotta raffigurante putti che sorreggono una ghirlanda.
A partire dal 1625 il palazzo fu sede dei governatori spagnoli e dopo il 1713 di quelli della Repubblica di Genova.
Interventi di ristrutturazione degli interni avvennero al momento del passaggio dell'infanta Margherita di Spagna, che soggiornò nel palazzo nel 1666 prima di intraprendere il suo viaggio verso Vienna.
Nel 1789, Benedetto Andrea Centurione, governatore genovese del Finale, promosse un radicale rifacimento dell'edificio, come confermato dal lungo fregio in facciata.
Il fronte principale fu ampliato, escludendo dalla vista la loggia medievale e venne aperto il nuovo ingresso centrale dove fu collocato un architrave con motivi militari e le spalle bombate di un camino cinquecentesco proveniente dalla demolizione di Castel Gavone. La decorazione allegorica dipinta intorno al portale risale al periodo napoleonico.
Nel 1782, con l'abbattimento della cosiddetta "Casa del Cancelliere", fu creata l'attuale piazza, alla quale fanno da fondale le facciate di palazzo Cremata, a oriente, e di palazzo Arnaldi, a occidente, con una leggiadra decorazione di metà Ottocento in stucchi che incorniciano le finestre dei diversi piani.