Der Name des Hügels Paleokastro in der Bedeutung ‚Alte Burg‘ oder ‚Alte Festung‘, auf dem die Fortezza errichtet wurde, weist auf eine Befestigung im Altertum hin, die sich an dieser Stelle befand. Die Venezianer sollen beim Bau ihrer Festung Reste antiker Gebäude und Konstruktionen abgerissen oder durch Erdaufschüttungen überdeckt haben. Dies wird durch einen Bericht des Mediziners und Botanikers Onorio Belli gestützt, der im Jahr 1586 über Säulen und Reste eines alten Tempels im Inneren der Fortezza schrieb. Innerhalb und außerhalb der Festung in den Fels geschlagene Zeichen weisen auf die ehemalige Existenz eines Heiligtums auf dem Paleokastro, bei dem es sich wahrscheinlich um den von dem römischen Sophisten Claudius Aelianus im 3. Jahrhundert erwähnten Tempel der Rokkaia Artemis (Diana von Rhoccaea) handelt. Man nimmt an, dass er Teil der Akropolis der antiken Stadt Rhithymna (Ῥίθυμνα) war.[1]

In der venezianischen Zeit ab 1204 beziehungsweise 1210 bestand zunächst eine Befestigung östlich des alten Hafens von Rethymno, das Castrum Rethemi oder Castel Vecchio. Nach der Plünderung der Vororte durch die Korsaren in osmanischen Diensten Khair ad-Din Barbarossa 1538 und Turgut Reis 1540 entschloss man sich, Rethymno mittels einer Stadtmauer zu befestigen. Die Planungen des Veroneser Architekten Michele Sanmicheli von 1537/38 wurden ab 1540 entsprechend umgesetzt. Im Jahr nach der Fertigstellung der Stadtmauer 1570 wurde Rethymno am 7. Juli 1571 bei einem Überfall des Korsaren Uludsch Ali Pascha in Brand gesetzt und die Stadtmauer sowie das Castel Vecchio niedergerissen. Dies nahm man zum Anlass, den Bau einer Festung auf dem Paleokastro zu beschließen, in deren Inneren die Häuser der Stadt errichtet werden sollten. Die Grundsteinlegung der Fortezza erfolgte 1573 unter dem Rektor Alvise Lando.[1]

Geplant wurde die Festungsanlage der Fortezza durch den Architekten Sforza Pallavicini. Im Jahr 1578 waren die Bauarbeiten an der Außenmauer unter Leitung des Ingenieurs Gian Paolo Ferrari beendet. Bis dahin hatten jedoch die Bürger von Rethymno ihre Häuser nach dem Brand von 1571 wieder aufgebaut, wobei als Baumaterial auch Steine der zerstörten Stadtmauer verwendet wurden. Weiterhin stellte man fest, dass die Fläche innerhalb der Fortezza zu klein war, um dort sämtlichen Bürgern Platz für ihre Häuser zu bieten. Deshalb sah man im Folgenden vor, die Festungsanlage lediglich als Zufluchtsort für die Bevölkerung sowie als Sitz der venezianischen Verwaltung, des lateinischen Bischofs und der Armeeverwaltung zu verwenden.[2]

Bis 1580, in der Amtszeit des Rektors Bernardo Pollani, waren die Wohnung des Armeekommandanten Manoli Mormori, von 1576 bis 1582 Kommandant der Stadt, 54 Soldatenunterkünfte und 3 Zisternen fertiggestellt sowie der Grundstein des Palazzo Publico, dem Amtssitz des Rektors, westlich des zentralen Platzes gelegt. Die Einweihung des bis 1582 auf einer Fläche von 33,06 × 22,62 Meter errichteten Palazzo Publico erfolgte 1583 durch den in diesem Jahr neu eingesetzten Rektor Anzolo Barocci. Doch erst unter seinem Nachfolger Benetto Bembo, der von 1585 bis 1588 diese Funktion bekleidete, wurden 1587 die Kanonenscharten vervollständigt und die Arbeiten an den Brustwehren weitergeführt. Auch die Erdarbeiten waren noch nicht abgeschlossen. Weiterhin errichtete man Lagerhäuser, zwei weitere Zisternen, ein Munitions- und ein Waffenlager. In den Zeiten der Rektoren Nicolo di Priuli (1588 bis 1591) und Luca Falier (1591 bis 1593) wurden die meisten Arbeiten an der Fortezza abgeschlossen.[3]

Nachdem am 17. August 1645 Chania (Canea) als eine der ersten Städte Kretas durch das Osmanische Reich unter der Herrschaft Sultan İbrahims erobert wurde, standen die Osmanen ein Jahr später, am 29. September 1646, vor Rethymno (Retimo). Die schlecht befestigte Stadt wurde durch die Truppen ihres Oberbefehlshabers Hussein Pascha (türkisch Hüseyin Paşa, auch die vorangestellten Beinamen Gazi oder Deli tragend) nach 14 Tagen im Oktober 1646 eingenommen. Bei den Kämpfen fielen auf venezianischer Seite General Cornaro und der Provveditore Molino. Nach der Belagerung der Fortezza, in die sich die Bevölkerung der Stadt zurückgezogen hatte, und der Sprengung und Erstürmung des großen Turmes an der Meerseite der Festung am 13. November 1646 ergaben sich die Verteidiger am darauf folgenden Tag. Die Venezianer konnten günstige Kapitulationsbedingungen aushandeln und erhielten freien Abzug nach Iraklio (Candia).[4][5]

In osmanischer Zeit wurde an den Befestigungsanlagen der Fortezza kaum etwas verändert. Einzig zum Schutz des Haupttores im Osten errichtete man vor diesem die fünfeckige „kleine“ Festung, den Bau, in dem sich heute das Archäologische Museum von Rethymno befindet. Im Innenraum der Fortezza wurde die katholische Bischofskirche San Nicolo durch die Sultan-Ibrahim-Moschee ersetzt und eine Anzahl weiterer Häuser gebaut. Später, nach der Abwanderung der Osmanen, zogen die ärmeren Schichten der Stadt in die verlassenen Häuser in der Festung.

Während der deutschen Besatzungszeit (1941–1945) diente die Festung dem deutschen Heer als Stützpunkt und einige Gebäude wurden in Kasernen und Gefängnisse umgebaut.

Die bis dahin innerhalb der Festungsmauern wohnenden Menschen wurden in neue Häuser außerhalb der Stadt umgesiedelt. Die Ende des 19. Jahrhunderts errichteten zwei kleinen Kirchenbauten in der Festung, Agia Ekaterini und Agios Theodoros Trichinas, blieben erhalten, das Minarett der Moschee hingegen riss man nach der Unabhängigkeit vom Osmanischen Reich ab. Einziger Neubau in der Fortezza ist das 1986 auf der Bastion Agios Ilias eingeweihte Freilufttheater.[6]

Die Belagerung von Rethymno. www.rethymnon.gr, archiviert vom Original (nicht mehr online verfügbar) am 5. Juni 2009; abgerufen am 9. Februar 2011.   Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/www.rethymnon.gr