Ostrvo duguje svoje ime Kefalosu, mitskom heroju. Ima i drugačijih teorija o poreklu imena ostrva. Jedna kaže da je ime izvedeno iz činjenice da je ostrvo najveće u jonskoj grupi (na grčkom se glava kaže kefali) a postoji i teorija da je „glava“ u osnovi imena ostrva zbog samog oblika koje isto ima.
Postojala su nekada četiri glavna grada na ostrvu, Sami, Pali, Krani i Proni. Ovo objašnjava zašto se ostrvo zvalo Tetrapolis (četiri grada) u tom periodu. Ti gradovi su bili samostalni i nezavisni te su imali svoju vojsku, novac i upravu. Kefalonija je učestvovala u Persijskom i Peloponeskom ratu na strani i Atine i Sparte. Takođe je poznata po Kiklopskim zidinama.
Mitski heroj Kefalos po kome je ostrvo najverovatnije nazvano
Filip Makedonski je pokušao da napadne ostrvo 218. godine pre Hrista. Pobeđen je zahvaljujući pomoći Atinjana. Rimljani su osvojili ostrvo 187. godine pre Hrista nakon par meseci borbe protiv otpora lokalnog stanovništva. U to vreme je uništen antički Akropolj u Samiju. Rimljani su koristili ostrvo kao stratešku tačku za osvajanje kopnenog dela Grčke.
Oni su dakle pretvorili Kefaloniju u važnu pomorsku bazu. Tokom tog razdoblja, ostrvo je mnogo pretrpelo zbog napada raznih osvajača i gusara. Gusarske pretnje su se nastavile tokom vizantijskog razdoblja (od 4. veka). Najopasniji gusari su bili Saraceni, severoafrički.
U 11. veku ostrvo je palo pod franačku vlast i to je bio kraj vizantijskog perioda. Kefaloniju su potom uzastopno osvajali Normani, Orsini, Andeanci i Tokanci. Prvi turski napad je izveo Ahmed – paša, 1480. godine. Paša i njegove trupe vladale su ostrvom kratko ali su ga uništili kada su otišli.
Sledeći istu sudbinu kao i ostatak jonskih ostrva, Kefalonija je došla pod vlast Mlečana i Španaca. Politički i vojni centar ostrva su u tom periodu bile tvrđave Agios Georgios i Asos koje su uništene u zemljotresu 1757. godine. Prestonica je preseljena u Argostoli i još uvek je tu.
Tokom venecijanske dominacije atmosfera je bila prilično konfliktna jer je društvo bilo podeljeno u tri klase. Plemićka, najbogatija i najmoćnija, imala je sve privilegije i koristila ih je protiv drugih društvenih klasa.
Mletačka vlast se završila 1797. dolaskom Francuza koji su bili toplo pozdravljeni od strane stanovnika ostrva jer im je Napoleon obećao da će ih osloboditi (kao i ostatak jonskih ostrva) od oligarhijskog sistema koji su stvorili Mlečani.
Francuzi su javno spalili Zlatnu knjigu u kojoj su bila zapisana imena i privilegije plemića. Francuzi su kasnije poraženi od strane savezničke flote Rusa, Turaka i Engleza.
Jonska država je osnovana u Konstantinopolju 1800. godine i bila je pod nadzorom sultana. Plemstvo je ponovo dobilo svoje privilegije. Nakon zahteva većine stanovnika organizovani su demokratski izbori 1802. godine i donet je novi Ustav 1803.
Ostrvo je ponovo palo pod francusku dominaciju 1807. ali je novi Ustav zadržan. Nakon Ugovora iz Pariza, 1809. godine, jonska ostrva su došla pod vlast Engleza pošto su osnovane „Ujedinjene države jonskih ostrva“.
Nikolas Kejdž u filmu “Mandolina kapetana Korelija”
Tokom engleskog razdoblja su izgrađene važne građevine od javnog interesa uključujući britansko groblje Drapanos, De Boset (Drapano) most u Argostoliju, svetionik Agii Teodori i impresivno Opštinsko pozorište Kefalonije. Uprkos činjenici da je Kefalonija, kao i ostala jonska ostrva ostala pod engleskom vlašću i izbegla turski jaram, njeni stanovnicu su finansijski pomagali grčku revoluciju za nezavisnost protiv Turaka koji su vladali ostatkom Grčke.
Kefalonija se konačno ujedinila s ostatkom nezavisne Grčke 1864. godine, u isto vreme kad i ostatak jonskih ostrva. Tokom Drugog svetskog rata, 1941. godine, ostrvo su okupirale italijanske trupe koje su bile u savezu s Nemcima. 1943. je Italija kapitulirala, ali su njene trupe odbile da napuste Kefaloniju. Za kaznu, nemačke snage su ubile više od 5.000 italijanskih vojnika. To je istorijska činjenica opisana u poznatoj knjizi „Mandolina kapetana Korelija“ koju je napisao Louis de Bernieres. Kasnije je snimljen i film koji je doprineo velikoj popularnosti ostrva u turističkom smislu.
Avgusta 1953. veliki deo ostrva je uništen u užasnom zemljotresu.
