Le prime notizie documentarie del Palazzo risalgono al 1284, quando il Capitano della Massa di Parte Guelfa Francesco de’ Frescobaldi acquistò parte dell’edificio turrito dei Pipini per farne la sede delle magistrature forestiere (Podestà, Capitano del Popolo, poi Vicario Regio e Commissario), del tribunale e delle prigioni. Questo primitivo nucleo corrisponde all’ampliamento duecentesco in laterizio della casa dei Pipini, affacciato sull’attuale piazzetta del Bacchino. Il Palazzo fu ampliato fra il 1334 e il 1338 a opera di maestranze fiorentine, che, in luogo di una porzione più antica della struttura dei Pipini, edificarono in pietra alberese l’attuale ala meridionale dell’edificio. L’elegante struttura merlata, con il bianco prospetto principale rivolto a est, è caratterizzata da ampie bifore e saloni interni a travicelli dipinti.

Successivi interventi ne modificarono in parte l’aspetto medievale esterno. Al Cinquecento risalgono alcune finestre crociate, poi ripristinate, e la vela dell’orologio, realizzata nel 1534 su progetto di Nanni Unghero. La scalinata esterna sul prospetto orientale serba il ballatoio cinquecentesco su arconi, mentre le rampe furono rinnovate nel Settecento e con il restauro ‘in stile’ del primo Novecento. Nella nicchia trecentesca posta sopra la porta di accesso del primo piano era collocata la statua in pietra di Roberto d’Angiò (insignito della Signoria della città), andata distrutta alla fine del Settecento. Dal 1587 all’inizio del XVIII secolo, parte del piano terreno fu adibita a sede del monte di pietà (presente in Prato fin dal 1476).

A partire dalla metà del Settecento il Palazzo ospitò uffici governativi del Granducato di Toscana, che furono decentrati in strutture più ampie e moderne nel corso dell’Ottocento. Ciò portò all’abbandono del Palazzo, che a fine secolo versava in pessime condizioni. Dopo aver considerato seriamente l’ipotesi della demolizione, tra il 1890 e gli anni Venti del Novecento si svolsero numerosi interventi di restauro; in concomitanza a questi lavori, nel 1912, venne inaugurata la Galleria Comunale, precedentemente ospitata nel Palazzo del Comune. Un ultimo, complessivo restauro è stato avviato nel 1998 e terminato nel settembre 2013 riportando il Museo alla città con la mostra Da Donatello a Lippi. Officina pratese.