Nel luogo dove sorge il palazzo, esisteva, dal 196 a.C. un tempio dedicato a Veiove, ricostruito nel I secolo d.C. secondo la forma con cui si è conservato. Era a pianta rettangolare con un piccolo portico sporgente su uno dei lati d’ingresso una pianta assai rara nei templi romani. 

Dell'antico tempio restano il podio in travertino, parte del portichetto e la cella. Accanto ad esso, nel 78 a.C. venne edificato il Tabularium come archivio pubblico romano, poiché vi venivano conservate le tabulae cioè le leggi e i documenti pubblici. 

Del Tabularium resta solo una galleria ad arcate che forse era un passaggio pubblico. Nel medioevo i resti romani furono inglobati in un fortilizio; nel 1143, alla nascita del libero Comune di Roma, ne divenne la sede e vi risiedettero i primi senatori. 

La prima forma del Palazzo Senatorio ci è tramandato solo da scarse fonti che lo rappresentano come un edificio con due torri, una della quali alloggiava la Patarina, la campana tolta a Viterbo come preda bellica. 

Alla fine del '300 il palazzo assunse il suo aspetto monumentale con la facciata a tre ordini d'arcate. Ma già nel corso dello stesso secolo il Palazzo cominciò a chiudersi entro le sue mura e molte arcate vennero murate. 

Dopo varie aggiunte e rimaneggiamenti, si giunse, per volere di papa Paolo III, al progetto di rinnovamento del complesso degli edifici capitolini, ideato nel 1537 da Michelangelo. In questo progetto, tra l'altro, compare la scala a doppia rampa e la balaustra che termina il palazzo, che doveva essere adorna di statue. Il progetto fu seguito da Michelangelo fino alla sua morte e fu sostanzialmente modificato dai suoi continuatori. 

La facciata attuale è della fine del '500 ed è opera di Giacomo della Porta e di Girolamo Rainaldi. Le due colossali statue di fiumi, il Nilo e il Tigri trasformato in Tevere, provengono dalle Terme di Costantino del Quirinale; al centro è la piccola statua di "Minerva - Dea Roma". 
La torre fu costruita tra il 1578 e il 1582 da Martino Longhi il vecchio. 

L'Assemblea Costituente della Repubblica Romana ebbe qui, nel 1849, la propria sede e vi fu anche disciolta dalle truppe francesi. Dal 1870 l'Aula Consiliare, che conserva alle pareti le bandiere del Comune e dei 22 Rioni e stemmi di papi e senatori, ospita il Consiglio Comunale di Roma.