In 1299, the commune and people of Florence decided to build a palace that would be worthy of the city's importance, and that would be more secure and defensible in times of turbulence for the magistrates of the commune. Arnolfo di Cambio, the architect of the Duomo and the Santa Croce church, began construction upon the ruins of Palazzo dei Fanti and Palazzo dell'Esecutore di Giustizia, once owned by the Uberti family. Giovanni Villani (1276–1348) wrote in his Nuova Cronica that the Uberti were "rebels of Florence and Ghibellines", stating that the palazzo was built to ensure that the Uberti family homes would never be rebuilt on the same location.
The cubical building is made of solid rusticated stonework, with two rows of two-lighted Gothic windows, each with a trefoil arch. In the 15th century, Michelozzo Michelozzi added decorative bas-reliefs of the cross and the Florentine lily in the spandrels between the trefoils. The building is crowned with projecting crenellated battlement, supported by small arches and corbels. Under the arches are a repeated series of nine painted coats of arms of the Florentine republic. Some of these arches can be used as embrasures (spiombati) for dropping heated liquids or rocks on invaders.