Chamado en orixe Palazzo dei Priori ou Palagio Novo, cambiouse o nome polo de "Pazo da Señoría", o organismo principal da República florentina, no século XV. Despois coñeceuse coma "Pazo Ducal", ao establecer alí a súa residencia Cosme I de Medici en 1540. Despois, en 1565, empezaría a chamarse Palazzo Vecchio ao terse mudado Cosme ao Pazo Pitti.
A primeira construción atribúese a Arnolfo di Cambio, que a iniciou en 1299 incorporando a antiga torre de Foraboschi na fachada. Trala morte de Arnolfo, en 1302, o pazo foi rematado por outros artistas, en 1314. A forma exterior do edificio é a dun paralelepípedo, e na fachada principal atópase a Torre de Arnolfo, un dos emblemas da cidade. En 1400 a torre e o xardín interior tiveron que ser reconstruídos, xa que corrían perigo de derrubarse.