L'edificio è situato sul lato est di Piazza XX Settembre, su un'area che già in epoca romana aveva ospitato edifici importanti, come documentato dalla presenza di mosaici risalenti alla fine II o inizi del III secolo d.C.

La parte più antica, che oggi ospita gli uffici e la direzione della Cassa di Risparmio di Fano, sorse per volere di Galeotto I Malatesta dopo il 1357, anno in cui divenne Vicario Apostolico, e di fatto Signore, di Fano.

Notevole è la grande volta trecentesca a crociera già facente parte della casa malatestiana e attualmente sede della presidenza della Fondazione Cassa di Risparmio di Fano. La torretta scalare cilindrica che è visibile dalla corte sul lato di mezzogiorno non è di facile datazione, ma si presume sia tra le parti più antiche del palazzo.

La parte più recente, quella che occupa il lato di tramontana ed è oggi sede di Pinacoteca e Museo Civico, fu invece fatta erigere da Pandolfo III Malatesta fra il 1413 ed il 1423. Attualmente l'edificio appare largamente rimaneggiato da vari interventi, fra cui va citato quello dell'architetto Alberto Calza Bini che nel 1929 operò varie aggiunte "in stile" alla struttura originaria. Rimangono comunque degne di nota le bifore gotiche in cotto lavorato presenti sia sul fronte nord orientale della corte che sul fronte posteriore, databili a dopo il 1420.

Lo scalone e la loggia furono ricostruiti come appaiono oggi nel 1544, per opera dello scalpellino Giovanni Bosso, in un tempo nel quale la signoria dei Malatesta era da tempo tramontata e nel palazzo si era insediato il civico Magistrato.

Notevole anche l'Arco Borgia Cybo (ultimi anni del 1400), che permette l'accesso da Piazza XX Settembre.
Nell'androne retrostante che conduce alla Corte si trova una nicchia con la Madonna dei Martinozzi, cinquecentesca, qui trasferita nel 1849 dal vicino Palazzo del Podestà.

Il palazzo è inoltre collegato al Palazzo del Podestà tramite un pontile, ricostruito ma presumibilmente presente anche nella struttura originaria.