Gavdos has supported a permanent population since Neolithic times. However, the island currently has very few permanent residents.
Gavdos has been identified as a possible site of the mythical Ogygia where Kalypso held Odysseus prisoner. Archaeological evidence showed that the Roman empire was active on the island. During this time the flora of the island was over exploited, this started a process of erosion which has continued to this very day.
Gavdos had approximately 8,000 inhabitants by 900 CE. During the Ottoman Empire's reign on the island, which lasted from 1665 until 1895, Gavdos was known as Gondzo. During this period the population decreased considerably to only 500 by 1882. A reference to Saracens on the island survives: the beach Sarakiniko ("of the Saracens").
In the 1930s the island was used as a place of exile of communists; more than 250 people were exiled including leading figures of the Greek movement, such as Markos Vafiadis. During World War II, allied forces evacuated some forces to Gavdos following the German victory in the battle of Crete.
Later on, the general phase of urbanization that started in other parts of Greece in the 1960s, took place in the 1950s on Gavdos. During that period the islanders exchanged their land on Gavdos with ex-Turkish land on Crete, which had now become exchangeable via the state. Upon settling in Crete they created a community known as Gavdiotika, which is part of the town of Paleochora
