Kefalonia is believed to have taken its name from the hero Cephalus. Perhaps the name of the inhabitants, Cephaloi, comes from the word "cephales" which may refer to Kefalonia's mountains, or to the fact that it is the biggest of the Ionian islands. The Cephallenes, subjects of the legendary king Cephalus, inhabitants of a kingdom which included Kefalonia (Same), neighbouring Ithaki, Zakinthos, Lefkada and a part of Akarnania, are first mentioned by Homer. Going farther back in time, no one can say for sure whether Taphus (possibly Cephalus' town) was the name of one town or of the whole island. Up to some point, the island would appear to have been governed as a unified whole. But Homer informs us that Odysseus took part in the Trojan War with 12 ships from Samos; from this we can safely assume that other towns were created later.

Thucydides refers to these towns as the Tetrapolis. Their names Pale, Crane, Same and Pronnoi have come down to us in the writings of the ancient authors Thucydides and Strabo, as well as on coins and inscriptions. They were named after the four sons of Cephalus, Samos, Pronnesos, Peleus and Cranius. The ancient geographer Strabo also called Kefalonia Melaina or Melane Epirus, because of its thick, dark forests.

The name Sami, taken from a Phoenician word that according to Strabo means high places, is mentioned in the Iliad in reference to the whole island.