The earliest possible evidence of a hominin presence on Crete comes from Trachilos, near Kissamos, where fossilized bipedal footprints with human-like characteristics have been discovered. A 2021 study dated the footprints to approximately 6.05 million years ago, although both their age and their attribution to an early hominin remain scientifically debated. Another study has proposed that the rocks preserving them are considerably younger, dating to approximately 3 million years ago.

The earliest clear archaeological evidence of a human presence on the island is much more recent. Dozens of stone tools, scrapers and hand axes discovered in the area of Plakias date back at least 130,000 years and may be considerably older, possibly up to 700,000 years old. They cannot be attributed with certainty to a particular human species, such as Homo erectus, but they provide evidence for the presence of archaic hominins on Crete. As the island was already separated from the mainland, these discoveries suggest that its early visitors were capable of crossing stretches of open sea. Paleolithic finds have also been reported in the area of Samaria.

Before these tools were discovered, scholars generally dated the first human arrival on Crete to the Neolithic period. An important prehistoric site is the cave of Skordalakia at Asfendou, where rock carvings depicting animals and hunting scenes have been found and attributed to approximately 8000 BC. Other finds and remains of dwellings have been identified in the area of Katsambas near Heraklion, while numerous traces of prehistoric habitation have also been discovered in caves.

Cavities near cave entrances were used as burial places, while parts of their interiors were arranged for habitation and the storage of supplies. A characteristic example is the cave of Gerani, where archaeologists discovered a pit filled with animal bones and, next to it, numerous small and large tools made of bone.