As orixes do castelo poden ser tan antigas como a fundación fenicia de Oea no século VII a.C.; as escavacións atoparon restos que datan da época romana. Como a rexión circundante, foi tomada polo Reino Vándalo ao redor do ano 439, recuperada
o Imperio Romano en 534, invadido por Amr ibn al-As en 642 ou 643, reconquistado polos bizantinos e de novo polo Califato Omeya a finais do século VII; despois baixo o goberno dos califatos abásidas (750-800), o emirato aghlabíde de Ifriqiya (800-909), o califato fatimí (século X) que o reformou nunha residencia real, o emirato Zirid de Ifriqiya e Banu Khazrun (século XI-1146), o reino normando de África (1146-58), o califato almohade (1158-1229), o emirato Hafsid de Ifriqiya (1234-1321), o Beni Ammar (1321-1401) e de novo o emirato Hafsid (1401-1510, con outro lapso a mediados do século XV).