Many historians believe Cefalu began as a fortress, belonging to the Himeraeans, and may very likely have been first peopled by refugees after the destruction of Himera.
 
 

Its name first appears in history at the time of the Carthaginian expedition under Himilco, 396 BC, when that general concluded a treaty with the Himeraeans and the inhabitants of Cephaloedium (Cefalu).
 
 

But after the defeat of the Carthaginian armament, Dionysius the Elder made himself master of Cephaloedium (Cefalu), which was betrayed into his hands. At a later period Cefalu again became independent, but apparently on friendly terms with the Carthaginians, on which account it was attacked and taken by Agathocles, 307 BC.
 
 

In the First Punic War, Cefalu was reduced by the Roman fleet under Atilius Calatinus and Scipio Nasica, 254 BC, -- by treachery and not by force of arms. Cicero speaks of Cefalu as apparently a flourishing town, enjoying full municipal privileges; it was, in Cicero's time, one of the 'civitates decumanae' which paid the tithes of their corn in kind to the Roman state. Cefalu also minted coins. No subsequent mention of it is found in history, but it is noticed by the geographers Strabo, Pliny, and Ptolemy, among the towns of Sicily, and at a later period its name is still found in the Itineraries.
 
 

During the Byzantine domination the settlement was moved from the plain to the current spur, although the old town was never entirely abandoned. In 858, after a long siege, it was conquered by the Arabs, and rechristened Gafludi. For the following centuries it was part of the Emirate of Sicily.