A great variety of fossils have been found within the area of the park. The oldest fossils have been found in the phyllites of Palaiokastro district and are plant residues of the carboniferous period (~300 million years). Typical and fairly common for this territory are rudist fossils, around 70 million years old, located at several sites within the Tripolitsa limestone; the most typical gorge site is the one above the Epano Zakros spring.

The Miocene era is represented within the park by one of the most impressive and significant fossils, that of the Deinotherium giganteum, an animal related to the elephant. Parts of the deinotherium’s skeleton have been found at two sites within the park, near the hamlets of Agia Fotia and Pano Zakros. Today, the deinotherium findings from the Kato Zakros excavation are on display at the Natural History Museum of Crete, in Herakleion, and some of their copies are exhibited at the Natural History Museum of Zakros.

Besides the deinotherium, a pig ancestor and a mastodont also lived here in the Miocene period, as indicated by findings of fossilised teeth discovered near Agia Fotia and in the Kato Zakros gorge, respectively.

Marine organism fossils of this period have been found at various sites and include:

  • Corals, typically found within reef limestone, mainly on Karoubes beach, within the Kato Zakros gorge and north-west of the Toplou Monastery gorge
  • Sea-urchins (Clypeaster) and bivalves (Chlamys) within marl and marlstone, typical specimens found north of Karoubes beach
  • Various foraminifera

The Pleistocene era is represented within the park territory with significant mammal fossils that used to live in the region; today are encountered in many sites, mainly on coastal locations.

These mammals include the following:

  • Deer (Candiacervus cretensis)
  • Hippopotami (Hippopotamus creutzburgi)
  • Elephants (Elephas antiquus)
  • Mice (Kritimys catreus, Kritimys, Clemmys)

Bone fragments of such animals have been found mainly on coastal caves and karstic cavities created within limestone rocks of the region, and, particularly, within the thin red clay sediments of their floors. Such sites have been identified in the area surrounding Mt. Traostalos, around Karoumbes Bay, on Fangromouro Hill and at Xerocambos.