I regesti angioini del 1272 fanno riferimento per una fornitura di miglio al Castrum Cephaludi, senza specificare se si tratti della Rocca, delle mura urbane o il complesso costituito da entrambi. Fonti documentarie attestano l'esistenza di un castellano già alla fine del XII secolo. Il castrum di Cefalù fu uno dei più importanti fortilizi demaniali dell'isola fino al XV secolo, con un prestigio in certe circostanze maggiore di quello del castello di Messina e dei due di Palermo. Sorgeva sulla Rocca, ma attualmente di esso sopravvive, in parte, la grande cinta muraria che chiudeva tutto il vasto terrazzo superiore del rilievo, seguendo il ciglio delle pareti. Rimangono inoltre tratti delle mura che cingevano la vetta della Rocca, un «Fano», cisterne, forni e alcuni avanzi di un Mastio, sempre sulla cima.
Il muro di cinta è piuttosto basso e merlato ed appare opera genericamente medievale, così come i resti del mastio.