Në vitin 1299, komuna dhe populli i Firences vendosën të ndërtonin një pallat që do të merrej me rëndësinë e qytetit dhe që do të ishte më i sigurt dhe i mbrojtshëm në kohë turbulluese për magjistratët e komunës.[1] Arnolfo di Cambio, arkitekt i Duomos dhe kishës Santa Croce, filloi ndërtimin mbi rrënojat e Palazzo dei Fanti dhe Palazzo dell'Esecutore di Giustizia, dikur në pronësi të familjes Uberti. Giovanni Villani (1276-1348) shkroi në Nuova Cronica se Uberti ishin "rebelë të Firences dhe Ghibellines", duke deklaruar se pallati është ndërtuar për të siguruar që shtëpitë e familjes Uberti kurrë nuk do të rindërtohen në të njëjtin vend.[1]

Ndërtesa kubike është bërë me gurë të ngurtë, me dy rreshta të dy dritareve gotike, secila me një hark trefolo. Në shekullin e 15-të, Michelozzo Michelozzi shtoi bareliev dekorative të kryqit dhe zambakëve fiorentin në spandrels mes trefoils. Ndërtesa është kurorëzuar me kalldrëm të çmuar të përkulur, të mbështetur nga harqe të vogla dhe corbels. Nën harqe janë një seri e përsëritur e nëntë stemave të pikturuara të republikës fiorentine. Disa nga këto harqe mund të përdoren si embrasures (spiombati) për rënien e lëngjeve të nxehta ose shkëmbinj mbi pushtuesit.

Ndërtesa e fortë, masive rritet nga kulla e thjeshtë me orën e saj. Giovanni Villani shkroi se Arnolfo di Cambio përfshinte kullën e lashtë të familjes Foraboschi (kulla e njohur si "La Vacca") në fasadën e kullës së re si nënstrukturë;[1] kjo është arsyeja pse kulla drejtkëndore (lartësia 94 metra) nuk është në qendër të drejtpërdrejtë në ndërtesë. Kjo kullë përmban dy qeli të vogla, të cilat, në kohë të ndryshme, burgosën Cosimo de' Medici (1435) dhe Girolamo Savonarola (1498). Kulla është emëruar pas projektuesi i saj Torre d'Arnolfo. Ora e madhe e kullës, me një dorë, u ndërtua fillimisht në vitin 1353 nga fiorentini Nicolò Bernardo, por u zëvendësua në vitin 1667 me një kopje të bërë nga Georg Lederle nga qyteti gjerman i Augsburgut (italianët i referohen atij si Giorgio Lederle i Augusta) dhe të instaluar nga Vincenzo Viviani.

Duke Cosimo I de 'Medici (më vonë të bëhej dke i madh) zhvendosi selinë e tij zyrtare nga pallati Medici në Via Larga në Palazzo della Signoria në maj 1540, duke sinjalizuar sigurinë e fuqisë së Medici në Firence.[2] Kur Cosimo më vonë u hoq në Palazzo Pitti, ai zyrtarisht riemërtoi pallatin e tij të mëparshëm në Palazzo Vecchio, "Pallati i Vjetër", edhe pse sheshi i qytetit, Piazza della Signoria, ende mban emrin origjinal. Cosimo autorizoi Giorgio Vasari për të ndërtuar një vendkalim mbi tokë, korridorin Vasari, nga Palazzo Vecchio, nëpërmjet Uffizi, mbi Ponte Vecchio në Palazzo Pitti. Cosimo gjithashtu kam lëvizur selinë e qeverisë në Uffizi.

Pallati fitoi rëndësi të re si selia e qeverisë së përkohshme të Italisë së bashkuar nga viti 1865-71, në një moment kur Firence ishte bërë kryeqyteti i përkohshëm i Mbretërisë së Italisë. Edhe pse shumica e Palazzo Vecchio tani është një muze, ajo mbetet si simbol dhe qendër e qeverisjes vendore; që nga viti 1872 ka vendosur zyrën e kryetarit të Bashkisë së Firences, dhe është selia e Këshillit Bashkiak. Kulla aktualisht ka tre këmbanat; më i vjetri ishte hedhur në shekullin e 13-të.