Il palazzo El Mechouar fa parte della cittadella omonima costruita nel 1145 sul luogo dove il sultano almoravide Yūsuf ibn Tāshfīn si accampò durante l'assedio di Agadir (l'antico nome di Tlemcen). La cittadella, di forma rettangolare, misura 200 metri di lunghezza e 150 m di larghezza, fu trasformata in un palazzo dal sultano zayyanide Yaghmurāsan ibn Zayyān.[1] Il palazzo-fortezza divenne la residenza ufficiale degli Zayyanidi.[2]

Dopo aver conquistato Tlemcen nel 1337 il sultano merinide del Maghreb al-Aqsa (Marocco) Abū al-Ḥasan ʿAlī si stabilì nel palazzo e ne fece la propria base operativa nel suo tentativo di unificare il Maghreb. Fu qui che nel 1339 sottoscrisse un'alleanza economica e militare con il visconte di Narbona Almarico III, ambasciatore del re Giacomo III di Maiorca.[3] La sua sconfitta a Qayrawan nel 1348 mise fine al dominio dei Merinidi sul Maghreb centrale e sull'Ifriqiya e il Mechouar tornò sotto il controllo zayyanide.

La cittadella e il palazzo furono ingranditi e abbelliti dai vari sultani Zayyanidi. Una moschea fu costruita nei primi anni del XIV secolo da Abū Ḥammū Mūsā I.[4]

Il corsaro ottomano Aruj Barbarossa conquistò la cittadella nel 1516 dopo che gli abitanti di Tlemcen lo chiamarono per cacciare il loro sultano Abū Ḥammū Mūsā III, che aveva giurato fedeltà agli spagnoli. Aruj controllò Tlemcen fino al 1518. L'ex sultano di Tlemcen fece appello agli spagnoli, che gli fornirono un esercito con cui assediò Tlemcen per sei mesi, Aruj riuscì inizialmente a fuggire, ma venne catturato e decapitato dagli spagnoli.[5]
Con la fine della dinastia zayyanide il palazzo iniziò a decadere, il restauro iniziò nel 2010.