The Cave Kokkines Petres at Petralona is located 46 kilometers to the southeast of Thessaloniki, close to the road that leads to the Kassandra peninsula, in western Chalkidiki. The discovery of the cave in 1960 and its investigation has made it the first important landmark and has marked the study of the Palaeolithic era in Greece.

Inside the cave, in stalagmitic material, a fossilized human skull was unearthed probably belonging to a 25 year old woman; its age was initially estimated to be 700,000 years but recent dating, based on more precise methods provided by the natural sciences, dates the skull to 200,000 years BP. According to a morphological examination of the skull, it belongs to the anthropological type Homo sapiens praesapiens. On comparing the skull to one from Steinheim in southeast Germany it was chronologically placed 350,000 years BP, that is the Lower Palaeolithic Period.
Skulls of the same antropological type were unearthed in the late '70s at Apidima Cave in Mani and their dating was initially estimated between 300,000 and 100,000 BP. The finds mentioned above, together with the anthropological remains of the Yarimburgaz Cave, close to Constantinople (excavations 1988-90), confirm that there had already been some kind of habitation in the Greek-Aegean area, arching from Thrace and Chalkidiki to the south Peloponnese by the earliest phase of the Palaeolithic.

Inside the Cave, traces of a hearth (fire), lithic and bone atrefacts and animal bones belonging to bears, deers etc., were found but their examination has not yet been completed.