Until the late nineteenth century, the history of Paleochora was, to all intents and purposes, the history of the fortress that dominates the village and the skyline. Although the area surrounding the village contains many remains of early settlements, Greek and Greco-Roman towns and cities and although there is some evidence of early settlement and pottery making to the east of the current town, little is known of the village before the Venetian foundation of the fortress in about 1280. The Venetians having taken the island from the Genoese in 1205, the Genoese having taken it from the Byzantines following the sack of Constantinople by the Western Crusaders in 1204, the fortress was constructed as part of the Venetian attempt to bring Crete under their control and was one of a series of fortifications also intended to reduce the endemic piracy of the Cretan coasts and to limit the possibility of a Byzantine counterattack.
The Selino Castle originally built by the Duke of Crete Marino Gradonigo, Cretan rebels demolished the fortress back in 1332. However, it was quickly rebuilt by the Venetians due to its strategic location.
The history of Paleochora goes hundreds of years back in time, starting in 1272 when a Venetian general, the Duke of Crete Marino Gradonigo, built the fort that became known as Kastelli Selino (Selino Castle). It fell to the Cretans during the revolt of 1332; one of the many revolutions that occurred during the Venetian occupation of the island.
The fortress, which endured several attacks during the centuries, was also targeted by the famous pirate Barbarossa, well-known on the island since much of Crete’s fortune is linked to his repeated attacks.
The fortress was sacked again in 1539, this time in a raid by the noted Ottoman Admiral Hayreddin Barbarossa Pasha, only to be rebuilt for a second time by the Venetians.
The last successful assault on the fort was in 1653; this time it fell to the invading Ottoman troops. With the Ottoman occupation the threat of piracy had been greatly reduced and, with the main commerce of the island now concentrated on the north coast, though the fortress was intermittently maintained and to some extent extended internally, the settlement around it appears to have decayed considerably. Eventually, by the early 1860s, the fortress and adjoining area were described as being abandoned but for a storage shed.
The Cretan Insurrection of 1866 brought Selino Kastelli to international attention when a British warship, acting against orders, evacuated a number of Christian Cretan refugees from the beaches; an act which subsequently lead to similar trips being made by French, Russian, Italian and Prussian vessels. In 1878 Ottoman troops withdrew from the fort as part of their concentration in the more populated north of the island. In May 1890 Cretan Christians evacuated Selino Kastelli after several brutal murders were carried out by Ottoman troops sent to the area to provide security from inter-communal violence then occurring and in February 1896 Ottoman troops were landed at the fortress en route to put down yet another rebellion. The Royal Navy appeared at Selino Kastelli again in 1897 when, in conjunction with other European warships, they evacuated Cretan Muslims from Kandanos and the villages around the fort, along with the few remaining Ottoman troops, leaving the area totally in the hands of the Cretan Christians.
From that time onwards, the village, now starting to be known more generally as Paleochora, meaning Old Ground/Stone/Buildings, started to expand. By the early 1940s, aided by an influx of people evacuated from Gavdos, Paleochora had a population approaching 900 and, along with Kandanos, was one of the commercial and administrative centers of the region.
The fortress was again occupied in May 1941, this time by German troops. The new invaders installed anti-shipping and anti-aircraft batteries on the fort, and remained in occupation of Paleochora until their withdrawal to Chania in October 1944. Paleochora was fortunate enough to avoid the worst excesses of the Greek Civil War and gradually over a period of twenty or more years grew in importance as new agricultural processes in the form of the greenhouse production of tomatoes and cucumbers became center in Kondoura, 5km outside Paleochora.
The 1970s brought the advent of modern tourism and with it a new role to add to that of being the agricultural, cultural and administrative center of the Selino district. In 2011, following a number of administrative and boundary changes, Paleochora, with a permanent population recorded in the 2001 census of around 2600, became the seat of the Municipality of Kandanos-Selino and now flourishes as the major center for tourism in the South West Crete.