Il Cardinale Egidio Albornoz, che nel 1357 (in nome del Papa) aveva strappato Cesena agli Ordelaffi, fece costruire un nuovo palazzo negli anni 1359-1362. Nel Palazzo Albornoz (oggi Palazzo Comunale) risiedevano le massime autorità cittadine. Dopo la Signoria dei Malatesta (1378-1465), la città passò sotto il dominio diretto del Papa che esercitò tale dominio tramite un Governatore che si stabilì definitivamente nel Palazzo magistrale, oggi Palazzo del Ridotto).

Nel 1467 Pietro Giacomo da Forlì e Agostino da Cesena eseguirono degli affreschi; altre decorazioni ed affreschi furono eseguiti nel '500 (alcune parti di questi affreschi si possono ammirare ancora oggi nell'ultimo piano del Palazzo). Nel 1523, al piano terra del Palazzo, venne costruito il grande portico o loggiato dove furono collocate numerose botteghe.
Nel 1720 il Palazzo diventò sede del municipio: le autorità municipali lasciarono il vecchio Palazzo magistrale davanti al Suffragio (che diventerà sede del Ridotto dei nobili o Palazzo del Ridotto) e si trasferirono nel Palazzo Albornoz (dove continuò a risiedere anche il Governatore).
Nel 1732 venne collocato nel salone comunale il busto di Papa Clemente XII Orsini che aveva restituito alla città (con la bolla "Permulta") gli onori e i privilegi aboliti dal Predecessore Benedetto XIII. Il busto fu eseguito dallo scultore romano Paolo Campi, la nicchia di Carlo Vogini. Il salone comunale (chiamato anche, da allora, sala clementina) venne trasformato in una galleria di emblemi e motti sulle virtù del pontefice (che nello stesso anno donò 5000 scudi per la costruzione di un grande ponte sul Savio che prese il nome di Ponte Clemente, oggi Ponte Vecchio). Il Palazzo Comunale subì altre trasformazioni: l'aspetto attuale è ottocentesco. A metà ottocento fu costruita, a ridosso del Palazzo, la caserma "Ordelaffi" che oggi è sede di vari uffici.