Si presume che la prima fortezza costruita nei pressi di quella attuale potrebbe risalire al IX o X secolo. Nel 1319 il Vescovo Tarlati diede inizio ai lavori di fortificazione della città tra cui la costruzione del Cassero di San Donato situato nel punto di estrema difesa della cittadella. Il Cassero di San Donato subì gravi danni a causa delle lotte cittadine e delle rivolte contro il Vescovo Tarlati e nel 1337 ceduta la fortezza ai fiorentini, venne ristrutturato. Quando gli aretini riacquistarono la loro indipendenza nel 1343 demolirono la fortezza per disprezzo nei confronti dei fiorentini, per poi ricostruirla nel 1344. Nel 1384 le truppe francesi rovinarono in parte la fortezza che venne ricostruita dai fiorentini, nuovamente tornati al potere che ultimarono i lavori nel 1398. Nel 1502 Arezzo, in atto di rivolta contro il dominio fiorentino, smantella in parte la fortezza, ma i fiorentini contrastando l'insurrezione la ricostruiscono avvalendosi di due importanti architetti, Giuliano da Sangallo e suo fratello Antonio il Vecchio, iniziando i lavori a partire dal 1505 su ordine di Cosimo I. Nel 1530 mentre nella Firenze repubblicana infuriano dure lotte, gli aretini si ribellano nuovamente danneggiando la fortezza. Successivamente Cosimo I diede inizio ai lavori di ristrutturazione che iniziarono nel 1538 e finirono nel 1560; rispettando l'originale disegno di Antonio da Sangallo il Vecchio. La Fortezza fino al 1782, non subisce ulteriori trasformazioni; se non che, nel 1800, le truppe francesi, tentano, senza riuscirci, di farla saltare con le mine. Verso la metà del '800 la famiglia Fossombroni acquista la fortezza, che nel 1893 su testamento, viene ceduta al Comune. Tra il 1896 e il 1904 lavori di restauro, trasformano la fortezza a pubblico passeggio, creando viali e ornamenti di piante.