La prima fase costruttiva di Palazzo Vecchio è quella che risale ad Arnolfo di Cambio (1299-1302), incaricato dal Comune di realizzare un edificio che ospitasse i Priori, ovvero i rappresentanti di quelle Arti Maggiori che governavano la Repubblica. Poggiando sulle rovine delle case degli Uberti, sul Palazzo dei Fanti e sul Palazzo dell'Esecutore di Giustizia, Arnolfo creava per la città il terzo dei suoi capolavori architettonici (dopo Santa Croce e il Duomo). Il modello, che è quasi una versione aulica del Palazzo del Bargello (costruito nel 1255), ricorda il tipico palazzo comunale toscano, ma si ispira anche al castello dei Conti Guidi a Poppi. L'aspetto è quello di un possente cubo rivestito di bugnato rustico (proveniente dalle cave della collina di Boboli), con due ordini di eleganti bifore trilobate e ingressi difesi da antiporte. In alto però Arnolfo crea, con un'audace soluzione, un ampio ballatoio merlato molto sporgente e appoggiato su archetti e mensole sotto cui vengono dipinti a ripetizione i nove stemmi del popolo e di Firenze. Alcuni di questi archi sono in realtà "caditoie" attraverso cui, in caso di guerra o di sommosse, far cadere sugli assalitori pietre o olio bollente.

Dal ballatoio spunta improvvisamente la torre, la più alta della città (94 metri), collocata fuori asse, tutta spostata a destra, per meglio rapportarsi all'asimmetria della piazza ma anche per incorporare un'antica torre. Qui, in una stanza detta "l'Albergaccio",saranno imprigionati Cosimo "il Vecchio" (1433) e fra' Girolamo Savonarola (1498).

La torre, detta "di Arnolfo" e terminata nel 1308, sarà poi conclusa con una cuspide, una sfera di bronzo e il Marzocco, cioè un leone che regge il giglio fiorentino. Il leone, animale forte e nobile, è uno dei simboli più antichi della città. La parola Marzocco potrebbe derivare da Mars, cioè Marte, protettore della città prima che la Firenze cristiana scegliesse San Giovanni. Una coppia di leoni fu tra l'altro ospitata fino al Settecento nell'area sul retro del Palazzo, detta per questo via dei Leoni.

Il carattere gotico della parte più antica dell'edificio resta visibile nella Sala d'Armi al piano terreno (sede di mostre temporanee del Comune), nel Salone dei Dugento al primo piano, e nell'ex Residenza dei Priori al secondo piano. Qui si possono ammirare in particolare la Cappella dei Priori (o della Signoria), con affreschi di Ridolfo del Ghirlandaio (1514), la Sala dell'Udienza e la Sala dei Gigli, dove si aprono la Cancelleria in cui lavorò Niccolò Machiavelli e la Sala del Mappamondo, già terrazzo e poi Guardaroba. In queste ultime due salette è ben visibile il confine fra il palazzo di Arnolfo e le prime modifiche: il territorio governato da Firenze stava crescendo e doveva crescere anche lo spazio per ospitarne le Magistrature. La successiva ristrutturazione vasariana lo raddoppierà addirittura.