Alla fine del XIII secolo, quando la città di Pistoia conobbe un periodo di grande floridezza economica e politica, si rese necessario costruire un palazzo più ampio e dignitoso per le magistrature cittadine che sino a quel momento avevano trovato sede provvisoria prima in alcune case private e poi in un più vecchio palazzo di cui oggi non rimane alcuna traccia.
Una tradizione diffusa nel secolo scorso, ma non confermata da alcun documento, vuole che il palazzo che ancora oggi è sede dell'amministrazione comunale sia stato fatto costruire dal podestà Giano della Bella, da cui la denominazione di Palazzo di Giano che ancora oggi lo contraddistingue. In realtà già prima della reggenza di quest'ultimo il comune aveva acquistato un nucleo di abitazioni poste all'angolo tra la piazza e l'attuale Ripa del Sale, in prossimità della prima cinta di mura. Viene così a cadere, stando alla più recente storiografia, un qualsiasi ruolo attivo da parte di questo podestà.
Le vicende costruttive del palazzo sono assai complesse e ancora oggi non del tutto chiarite, ma nonostante la scarsa documentazione è possibile ricostruirne le principali fasi.
Dopo la costruzione del primo nucleo, avvenuta alla fine del Duecento intorno al cortile in cui oggi è stato posto il Miracolo dello scultore pistoiese Marino Marini, il palazzo dei Signori Anziani e del Gonfaloniere di giustizia venne ampliato durante la prima metà del secolo successivo con l'aggiunta, tra l'altro, del portico di facciata che in un primo momento si limitò a sole quattro arcate. Un ulteriore ampliamento avvenne quando furono costruiti gli ambienti confinanti con la Ripa della Comunità, oggi destinati a sede di mostre temporane, e il palazzo fu innalzato fino al secondo piano. Si provvide anche alla costruzione della quinta arcata di facciata in modo da dare omogeneità al fronte che si caratterizza per la sua originalità rispetto ai moduli dell'architettura pubblica toscana. Verso la metà del XIV secolo il palazzo assunse l'aspetto che tutt'oggi lo caratterizza; sono infatti assai limitate le integrazioni avvenute nei secoli successivi e per lo più riguardano gli ambienti interni che si sono dovuti adattare nel corso del tempo alle nuove esigenze delle amministrazioni che si sono succedute.
Della prima metà del Seicento è comunque la costruzione del ponte che unisce il palazzo alla cattedrale in modo da consentire alle Magistrature cittadine di raggiungere direttamente il coro per assistere alle funzioni religiose.
Durante la massima affermazione del regime mediceo venne apposto sulla facciata il grande stemma centrale con le armi dei Medici sormontate dalla tiara papale e da grandi chiavi in onore di Papa Leone X, illustre membro di tale famiglia. Comunque sulla facciata non mancano insegne dell'epoca medioevale, quali la testa di marmo nero sormontata da una mazza in ferro che una leggenda popolare identifica con l'effige del traditore della città Filippo Tedici, anche se presumibilmente si tratta del ritratto di Re Musetto II di Maiorca, ucciso dal capitano pistoiese Grandonio dei Ghisilieri durante la conquista delle Baleari nel XII secolo. La testa del Tedici si trova invece sul portale di Sant'Andrea e la tradizione vuole che sia nera perchè in segno di spregio vi venivano spente le torce prima di entrare in chiesa.

Gli Orsi appaiono sull'arme pistoiese, la tradizionale scacchiera bianca e rossa, attorno alla metà del XIV secolo quando la città si liberò, con l'aiuto di Firenze, dall'assedio del ghibellino Giovanni Visconti. L'animale entrato nell'araldica pistoiese per confermare una identità da contrapporre a Firenze emblematicamente riconoscibile nel Marzocco sembra trarre origine dall'antica selva degli orsi, l'attuale Orsigna, estesi terreni montani da lungo tempo di proprietà comunale. Detto popolarmente il Micco l'orso ha perso ben presto ogni connotazione eroica per divenire, forse in ricordo dei rituali sacrifici che lo vedevano vittima designata, sinonimo di stupido, di allocco. Nel linguaggio popolare rimanere come un micco significa restare di stucco, fare la figura dello stupido. Quindi i micchi dello stemma della città, perduta irrimediabilmente ogni fierezza, restituiscono di questa e delle sue magistrature un'immagine domestica venata di ironia.