Σύμφωνα με το μύθο, το όνομά της, η Κεφαλονιά, το πήρε από το μυθικό πρόσωπο ονόματι Κέφαλος. Υπάρχουν πολλές εκδοχές για την ταυτότητά του. Άλλες λένε πως ήταν ο γενάρχης του γένους των Κεφαλιδών στην Αττική ο οποίος βοήθησε το βασιλιά των Θηβών, Αμφιτρύωνα στην εκστρατεία του κατά των πρώτων κατοίκων του νησιού, Τηλεβόων και ως ανταμοιβή δέχτηκε το όμορφο αυτό νησί. Εκεί παντρεύτηκε και απέκτησε τέσσερις γιούς: τον Κράνιο, τον Παλέα, τον Πρόννησο και τον Σάμιο. Τα τέσσερα αδέρφια με τη σειρά τους ίδρυσαν ο καθένας και μια ομώνυμη πόλη-κράτος που όλες μαζί έκαναν την θρυλική τετράπολις, ίχνη των οποίων σώζονται μέχρι σήμερα. Άλλες εκδοχές του μύθου, πάλι, τον θέλουνε γιό του Ερμή ή του Αίολου, ο οποίος εξορίστηκε από τον Άρειο Πάγο, όταν σκότωσε κατά λάθος τη γυναίκα του, την Προκρίδα, κόρη του Ερεχθίονα, σε ένα κυνήγι. Λόγος αυτής της τραγωδίας ήταν η θεά της αυγής Ηώ, η οποία, όντας ερωτευμένη μαζί του, τον είχε απαγάγει κάποτε και είχαν αποκτήσει τρεις γιούς μαζί. Η Προκρίδα, επιφυλακτική για την πιστότητα του συζύγου της, μετά από αυτή την περιπέτεια, τον κατασκόπευε στο κυνήγι. Εκείνος, νομίζοντας πως πρόκειται για κάποιο ζώο, την σκότωσε με ένα μαγικό δόρυ, δώρο της θεάς Άρτεμης, που ποτέ δεν έχανε το στόχο του.