Une localité berbère a succédé à Cartena : les sources musulmanes évoquent une cité nichée au fond d'un golfe, entourée de murailles et, signe de son importance, possédait des bazars, des bains et des jardins. En 1082, le prince almoravide Youcef Ibn Tachfine y construit un fort appelé Bordj El-Mehal qui, depuis, a été transformé en pénitencier. La ville tombe ensuite sous la domination des Zianides de Tlemcen, puis des Mérinides de Fès. C'est le prince Mérinide Abou al-Hassan qui a fait construire la mosquée en 1340. Cette mosquée, encore debout, a été fortement endommagée durant la conquête coloniale, l'édifice ayant servi de caserne jusqu'en 1845, date de la visite de Napoléon III. La cité n'a cessé de s'agrandir et de s'orner de monuments, elle acquit aussi la réputation de ville du savoir avec une vie mystique intense, ainsi qu'en témoignent les nombreux sanctuaires, le plus célèbre étant celui de Sidi Lakhdar Benkhelouf, poète (et panégyriste du Prophète), mystique et guerrier (il a participé notamment à la bataille de Mazaghran, en août 1558, au cours de laquelle les envahisseurs espagnols ont été écrasés.
