Po śmierci Juliana Arabowie przejęli całkowitą kontrolę nad miastem. Nazwali je po arabsku Sebtah, co przekształcono później w obecną Ceutę. Władał nim kalif Kordoby. Atakowane było ono często przez plemiona berberyjskie, najbardziej podczas buntu charydżytów. Po tej rewolcie dowodzonej przez Maysarę al-Haqira miasto zostało opuszczone. Zostało odbudowane w IX wieku przez Majakasa i jego plemię. Tak została zapoczątkowana dynastia Banu Isam. Po rozpadzie kordobańskiego kalifatu w 1031 roku istniało tu jedno z niewielkich państw, zwanych taifa.
W 1309 roku Ceuta została zdobyta przez Fez z pomocą Aragończyków. W XII–XIV w. swe faktorie handlowe miały tu wszystkie ówczesne potęgi Morza Śródziemnego: Genua, Piza, Wenecja, Katalonia, Marsylia. 22 sierpnia 1415 miasto zostało zdobyte przez Portugalczyków pod wodzą Henryka Żeglarza. Sukces ten został okupiony stratą zaledwie 8 zabitych. Głównymi celami władcy Portugalii Jana I były przywrócenie chrześcijaństwa, zdobycie saharyjskiego złota, stworzenie szlaków handlowych dla niewolników i kości słoniowej.