According to one theory, the hill on which the Fortezza is built was once, in a time lost in the mists of history, an island joined to Crete by a narrow strip of land. Over the centuries the channel silted up and the hill became part of the Cretan mainland.
The hill of Paleokastro ("Old Castle") was probably the site of the acropolis of ancient Rithymna with its Temple of Apollo and Sanctuary of Artemis, although this has not been proven to date. In the 3rd century AD, in the Roman period, there is a reference to a temple of Artemis Roccaea on the hill. In those times Rethymnon was an independent city with its own coinage but not a particularly powerful one.
During the Second Byzantine Period (10th-13th c. AD), a small walled settlement was established east of Paleokastro hill, the Castrum Rethemi or Castel Vecchio or Antico Castello ("Old Castle") as the Venetians later called it.
In the early 13th century the Genoese pirate Enrico Pescatore, an enemy of the Venetians who claimed Crete for himself, seems to have repaired the Byzantine fortifications surrounding the buildings of the small town near the harbour. The Castrum Rethemi was preserved after the Venetian occupation of the island in the 13th century, but unfortunately nothing remains today of the fortifications with their square towers and two gates.
The Venetians, as a marine power, intended to use Rethymnon as a shelter and intermediate base between Heraklion and Chania by building a harbour, even a small one. This led to Rethymnon becoming a city whose expansion necessitated the construction of new fortifications.
The events that followed in Crete from the first half of the 16th century onwards - the Turkish threat and the development of artillery after the invention and widespread use of gunpowder - led Venice to embark on the organisation of Crete's military defences and demonstrated the need for the Fortezza in Rethymnon. It was decided to build walls according to the plans of the Veronese architect Michele Sanmicheli. The foundation stone was laid on 8 April 1540 but the walls were only eventually completed just before 1570.
The walls of Rethymnon were only token defences, which were unfortunately not strong enough to withstand the attack of the corsair Ulu Ali Reis. He was an Italian who had been captured by Barbarossa's men and later become a Muslim, who rose to become Pasha of Algiers and fought many battles against the Christians in the Mediterranean. In 1571 Ulu Ali attacked Rethymnon with 40 galleys. The Venetians had abandoned the city, leaving behind only a skeleton guard of 100 men who were unable to resist for long. Ulu Ali easily scaled the defences and razed the city to the ground.
This destruction demonstrated the need for more effective fortifications. The local authorities, both Venetian and Cretan, the people of Rethymnon and the Venetian Senate, decided to build a fortress which could shelter all the houses in Rethymnon. The hill of Paleokastro was chosen as the most suitable site and work began on the Fortezza, one of the largest and most complete fortification works built in Crete under Venetian rule.