Il terreno sul quale venne edificato palazzo Madama fu ceduto nel 1478 dai monaci dell'Abbazia imperiale di Farfa alla Francia, che cercava un luogo ove ospitare i pellegrini francesi a Roma.

I primi importanti lavori di trasformazione del palazzo furono realizzati quando esso entrò in possesso della famiglia Medici. Il palazzo, infatti, venne restaurato su progetto di Giuliano di Sangallo e vi fu trasferito quello che era rimasto della biblioteca di Giovanni de' Medici - figlio di Lorenzo il Magnifico e futuro Papa Leone X - dopo la cacciata degli stessi Medici da Firenze.

Alla morte di Leone X, nel 1521, palazzo Madama venne assegnato a suo cugino Giulio de' Medici, che vi aveva lungamente abitato prima di salire al soglio pontificio come Clemente VII. Nel 1534 l'edificio fu ereditato da Alessandro de' Medici. Quando questi morì, nel 1537, venne assegnato in usufrutto alla moglie Margherita d'Austria, detta la "Madama" (da cui il palazzo prende il nome), figlia naturale di Carlo V e duchessa di Parma e Piacenza, che vi pose la sua residenza. Il palazzo rimase ai Medici ed ai Granduchi di Toscana fino al XVIII secolo.

Nel Seicento vennero effettuati notevoli lavori di ristrutturazione: una facciata barocca, progettata da Paolo Marucelli e ultimata nel 1642, prese il posto del precedente frontone asimmetrico e l'interno, sotto la direzione di Romano Monanni, si arricchì di soffitti decorati e di fregi.

I Medici, però, non si servirono più del palazzo finché, nel 1725, non andò ad abitarvi Violante di Baviera, cognata di Gian Gastone de' Medici, ultimo rappresentante della famiglia. Palazzo Madama visse allora un ultimo periodo di splendore, fu teatro di balli e feste e sede dell'Arcadia e dell'Accademia dei Quirini.

Nel 1737, alla morte del Granduca Gian Gastone, il Granducato di Toscana passò dai Medici ai Lorena, e con esso anche palazzo Madama. Quest'ultimo, nel 1755 fu acquistato da Papa Benedetto XIV e divenne palazzo pubblico dello Stato Pontificio. Il palazzo fu interessato da importanti interventi di ristrutturazione: fu aperto un secondo cortile dove oggi c'è l'Aula e fu sistemata la piazza antistante la facciata, affidata a Luigi Hostini.

Negli anni successivi vi furono installati, fra l'altro, gli uffici del tribunale e la sede della polizia. Da tale ultima destinazione del palazzo trae origine il termine dialettale "La madama", talvolta usato a Roma ancora oggi per definire le forze dell'ordine.

Palazzo Madama ospitò l'ufficio centrale della Repubblica franco-romana nel 1798-99.

Pio IX lo destinò a sede del ministero delle finanze e del debito pubblico e sembra che sulla loggia esterna del palazzo a piazza Madama venissero estratti - a partire dal 1850 - i numeri del lotto (l'estrazione fino ad allora era avvenuta a palazzo Montecitorio). Dal 1851 l'edificio ospitò anche gli uffici delle poste pontificie.

Nel febbraio del 1871 palazzo Madama venne scelto come sede del Senato del Regno. Questo evento rese necessari ampi lavori di adattamento: nello spazio del cortile delle poste pontificie, su progetto dell'ingegner Luigi Gabet, fu realizzata l'Aula dove il Senato del Regno si riunì per la prima volta il 28 novembre 1871.

Attualmente a palazzo Madama hanno sede l'Aula, alcuni Gruppi parlamentari, gli uffici della Presidenza e del Segretariato generale, nonché alcuni servizi ed uffici più direttamente connessi con l'attività parlamentare.