Senajos laikos pilsēta bija zināma kā Pistorija (Pistoria). Tajā dzīvoja galli, ligūri un etruski. 6. gadsimtā p.m.ē. tā nonāca Senās Romas kontrolē un bija zināma ar latīņu nosaukumu Pistorium vai Pistoriae. 5. gadsimtā Pistoija kļuva par bīskapiju. 11. gadsimtā tā kļuva par brīvu komūnu, bet 1329. gadā nonāca Florences ietekmē.
Saskaņā ar leģendu, no pilsētas nosaukuma ir radies vārds "pistole", kuras tur sāka ražot 16. gadsimtā.