Heraklion is close to the ruins of the palace of Knossos, which in Minoan times was the largest centre of population on Crete. Though there is no archaeological evidence of it, Knossos may well have had a port at the site of Heraklion as long ago as 2000 BC.
The present city of Heraklion was founded in 824 by the Saracens who had been expelled from Al-Andalus by Emir Al-Hakam I and had taken over the island from the Eastern Roman Empire. They built a moat around the city for protection, and named the city ربض الخندق, ("Castle of the Moat"). The Saracens allowed the port to be used as a safe haven for pirates who operated against Imperial shipping and raided Imperial territory around the Aegean.
In 961, Imperial forces under the command of Nikephoros Phokas, later to become Emperor, landed in Crete and attacked the city. After a prolonged siege, the city fell. The Saracen inhabitants were slaughtered, the city looted and burned to the ground. Soon rebuilt, the town of Chandax remained under Greek control for the next 243 years.
In 1204, the city was bought by the Republic of Venice as part of a complicated political deal which involved among other things, the Crusaders of the Fourth Crusade restoring the deposed Eastern Roman Emperor Isaac II Angelus to his throne. The Venetians improved on the ditch of the city by building enormous fortifications, most of which are still in place, including a giant wall, in places up to 40 m thick, with 7 bastions, and a fortress in the harbour. Chandax was renamed Candia and became the seat of the Duke of Candia, and the Venetian administrative district of Crete became known as "regno di Candia" (kingdom of Candia). The city retained the name of Candia for centuries and the same name was often used to refer to the whole island of Crete as well. To secure their rule, Venetians began in 1212 to settle families from Venice on Crete. The coexistence of two different cultures and the stimulus of Italian Renaissance led to a flourishing of letters and the arts in Candia and Crete in general, that is today known as the Cretan Renaissance.
After the Venetians came the Ottoman Empire. During the Cretan War (1645–1669), the Ottomans besieged the city for 21 years, from 1648 to 1669, perhaps the longest siege in history. In its final phase, which lasted for 22 months, 70,000 Turks, 38,000 Cretans and slaves and 29,088 of the city's Christian defenders perished. The Ottoman army under an Albanian grand vizier, Köprülü Fazıl Ahmed Pasha conquered the city in 1669. Under the Ottomans, the city was known officially as Kandiye (again also applied to the whole island of Crete) but informally in Greek as Megalo Castro (Μεγάλο Κάστρο; "Big Castle"). During the Ottoman period, the harbour silted up, so most shipping shifted to Chania in the west of the island.
In 1898, the autonomous Cretan State was created, under Ottoman suzerainty, with Prince George of Greece as its High Commissioner and under international supervision. During the period of direct occupation of the island by the Great Powers (1898–1908), Candia was part of the British zone. At this time, the city was renamed "Heraklion", after the Roman port of Heracleum ("Heracles' city"), whose exact location is unknown.