Costruito agli inizi del XIII secolo, il Palazzo fu la prima sede del governo cittadino, ossia del Podestà, la più importante autorità del Comune. Sotto le volte del portico si radunavano mercanti e artigiani, mentre al primo piano c'erano gli uffici dei notai (che si sposteranno poi nell'omonimo palazzo). Il palazzo era ed è sormontato dalla Torre dell'Arengo, la cui campana grande - detta il Campanazzo - fu innalzata nel 1453 da A. Fioravanti e suona solo in occasione di importanti avvenimenti. A partire dal 1484 ebbe inizio una ristrutturazione, per volere del Signore di Bologna - Giovanni II Bentivoglio - che desiderava abbellire il palazzo con forme rinascimentali, ma i lavori rimasero incompiuti perché egli fu cacciato da Bologna a furor di popolo: in particolare, non furono mai eseguiti i trafori delle finestre ed il cornicione.
Il Palazzo del Podestà si presenta con un ampio portico sovrastato da loggia ed è ornato da eleganti fasce di bugnato e da alte colonne che serrano gli archi. La superficie esterna si presenta in mattoni sagramati e membrature in arenaria scolpita, una diversa dall'altra. I quattro pilastri angolari che sorreggono la torre formano il cosiddetto "Voltone del Podestà": nel 1525, il voltone fu decorato con pitture e sui pilastri furono poste le statue dei santi protettori della città (San Petronio, San Procolo, San Domenico, San Francesco), statue realizzate in terracotta da Alfonso Lombardi. Il voltone ha una particolare proprietà: i visitatori possono parlare tra di loro, anche a bassa voce, dagli angoli opposti del voltone stesso.
La balaustrata, che era a parapetto, fu nel 1604 ridotta com'è ora da Pietro Fiorini: il portico ebbe grandi restauri nel 1837-1842 e la facciata nel 1887. Recentemente, la facciata del palazzo è stata restaurata per il progetto di Bologna 2000. Il gran salone servì da Teatro Pubblico dal 1581 al 1767, poi fu usato come campo di gioco del pallone, e infine fu trasformato in palestra per i pompieri; è stato decorato da A. De Carolis, la cui morte (1928) ha impedito il compimento definitivo dell'opera fastosa.