Luego d'a invasión islamica d'a peninsula iberica, a redolada de Tudela quedó en mans d'a familia d'os Banu Qasi, una familia d'orichen hispano-godo convertita a lo Islam. Ista familia teneba conexions con os primers reis d'o reino de Pamplona, pero en 802 Amrus ben Yusuf, que yera o gubernador andalusí d'a Marca Superior, establió una nueva ciudat fortificata en l'actual Tudela (clamata Al-Tutili), ta cosirar y controlar as penetracions d'o reino pamplonés enta o sud. Ista ciudat s'establió encara que en o mesmo lugar ya i existiba una chicota comunidat musulmana, profitando d'as condicions esfensivas de Tudela, con o suyo pueyo en a marguin sud d'o río Ebro. A nueva ciudat esdevenió a escape un important centro economico, politico y melitar, con a suya huerta de regano contino con as auguas d'o Ebro.