The first stage in the building of Palazzo Vecchio dates from the time of Arnolfo da Cambio (1299-1302), who was commissioned by the City Council to carry out a building suitable for the Priors, the representatives of the Main Guilds who then governed the Republic. Arnolfo created the third of his architectural masterpieces in the city (after Santa Croce and the Cathedral) by building the palace on top of the ruins of Palazzo dei Fanti and Palazzo dell'Esecutore di Giustizia, once the property of the Uberti family. The design, which is almost identical to Palazzo del Bargello (built in 1255), looks like many of the typical Tuscan council palaces, but was also inspired by the castle of the Counts Guidi at Poppi.

The exterior is rather like a ponderous cube covered in rustic stonework (from the quarries on the hill of Boboli), with two rows of elegant two-light trefoil windows and entrances protected by double doors. Arnolfo finished it off at the top using the daring solution of a wide projecting crenellated gallery supported by small arches and corbels, with the nine coats of arms of the people and Florence painted in repetition below them. Some of the arches are really embrasures used for "dropping" stones or boiling oil on the attacking forces in times of war or revolt.

The tower, the highest in the city (94 metres), soars up unexpectedly from the balcony; it is positioned off-centre, towards the right, partly to fit in better with the lack of symmetry of the square, but also in order to incorporate an ancient tower.Cosimo "the Elder" (1433) and Fra Girolamo Savonarola (1498) were imprisoned here in a room known as the "l'Albergaccio" (Hotel).

The tower, known as "Arnolfo's tower", was completed in 1308, and later topped with a cusp, a bronze sphere and the Marzocco, or lion, holding up the Florentine lily. The lion, a strong and noble animal, is one of the oldest symbols of the city. The word "Marzocco" probably came from Mars, the protector of the city before Christian Florence decided to choose St. John. A pair of lions were in fact kept in a cage at the rear of the palace until the 18th century, in fact Via dei Leoni gets its name from them).

The Gothic characteristics of the oldest part of the building can still be seen in the Arms Room on the ground floor (used for the temporary exhibitions organized by the City Council), in the Hall of the Two Hundred on the first floor, and what was once the LINK) Residence of the Priors, on the second floor. Here it is possible to admire the Chapel of the Priors (or the Signoria), with frescoes by Ridolfo del Ghirlandaio (1514), the Hall of Audience and the Room of the Lilies, which both open onto the Chancery where Niccolò Machiavelli used to work, and the Room of Maps, originally a terrace and later a Storeroom. The difference between Arnolfo's palace and the first alterations can be seen very clearly in these last two rooms: the territory ruled over by Florence was growing, therefore the space needed to house the Magistrates had to be enlarged as well. Vasari's later restructuration was to double it in size.