Época musulmana (siglos VIII-XII d.C.) Hasta su fortificación o re-fundación en el año 802, Tutela debió ser una plaza muy poco importante, despoblada y con muy pocas defensas. Tutela fue probablemente conquistada por el mulsumán Ayub el Lajimita alrededor del año 716, sin apenas oposición.
En el 802,[7 Tutela fue fortificada (y re-fundada como Al-Tutili) por Amrùs ben Yusuf, quien había sido nombrado gobernador de la Marca Superior por el emir Al-Hakam I. Amrùs concentró un gran ejército en Tutela, reconstruyendo y aprovisionando la plaza de Al-Tutili como una posición clave defensiva de la Marca Superior; su finalidad fue proteger las tierras ribereñas del Ebro de las incursiones de vascones y francos. Amrùs comenzó a reconstruir la Tutela histórica desde el cerro de Santa Barbara, en donde ubicó la Alcazaba. Seguramente su decisión fue favorecida por la existencia de algún viejo castillo visigodo, que sin duda él reconstruyó radicalmente para convertirlo en el núcleo preurbano de la ciudad. Desde ese enclave, Al-Tutili comenzó a poblarse lentamente monte abajo, primero hasta el río Mediavilla, siendo su perímetro fuertemente fortificado. Convirtió a Al-Tutili en la capital de la comarca gracias a la riqueza de la agricultura, ganadería y las distintas artesanías,[2] alcanzado en el siglo IX una población de unos 3.000 habitantes. A principios de este siglo, se debió construir una primera mezquita mayor, que seguramente se corresponde con la Mezquita de la Al-Hamdaka.
Al-Tutili fue el lugar permanente de residencia de Musa ben Musa, Musa II, el célebre “moro Muza”, que mantenía relaciones, incluso parentesco, con las casas señoriales de Vasconia. Su poderío fue tal que llegó a considerarse como el “Tercer Rey de España”, tras el emir Abd al-Rahman II de Córdoba y el rey astur Ordoño I de Oviedo. Durante su mandato y el de sus sucesores, en los siglos IX-X, Al-Tutili experimentó una gran expansión, llegando hasta las fronteras del río Queiles y alcanzando un gran esplendor económico y cultural. El recinto de la ciudad fue, de nuevo, fuertemente amurallado, teniendo como fosos naturales el Queiles y el propio Ebro. La nueva muralla de la ciudad tenía multitud de torreones vigía y se conoce la existencia de, al menos, 7 puertas: las de Albazares, de Zaragoza, del Mercado, de Calahorra, de Leza, de Ribotas y de Garoz. La medina fue militarmente reforzada por un sistema de torres vigía, llamadas atalayas (talias), situadas a extramuros (entre ellas la Torre de San Julián, la Torre de la Judía, la Torre Roya y, finalmente, la Torre Monreal, la única que se conserva). El espectacular puente de Tudela sobre el río Ebro, con una longitud de 360 metros y 17 arcos, pudo ser obra de los musulmanes, a imitación del que había en la mismísima Córdoba.
La importancia que adquirió Al-Tutili da fe la Mezquita Mayor, el zoco (Mercalete Vetere), una alcaicería, iglesias para los mozarábes, barrio judío con sinagogas, baños públicos y un abigarrado caserío al abrigo de la Alcazaba que estuvieron supeditadas a Al-Ándalus como frontera de dos fes religiosas: la musulmana y la cristiana. Aunque seguramente hubo muchas más, se tiene constancia de la existencia de al menos tres mezquitas en la medina tudelana, citadas en diversos escritos al finalizar la dominación musulmana: la Mezquita Mayor (ubicada en la misma posición que actual Catedral), la de la Mezquita de la Al-Hamdaka (situada en la actual Plaza de San Salvador) y una tercera emplazada en la puerta de Zaragoza.
La Mezquita Mayor de Tudela se construyó a mediados del siglo IX bajo la iniciativa del rey Musa. Esta primera mezquita, de aspecto arcaico, debió ampliarse, modificándose en lo estructural y lo ornamental con el paso del tiempo. Parece ser que, a principios del siglo X, fue saqueada y quemada por el rey navarro Sancho Garcés I. Luego se reformó y amplió a comienzos del XI bajo el mecenazgo de los Tuyibies durante el taifado de Zaragoza, concretamente con Mundir I, teniendo por modelos indiscutibles las mezquitas de Córdoba y Madinat al-Zahra.
La población se incrementó por causas político-militares y económicas, y fue foco de inmigración que atrajo contingentes humanos de los lugares cercanos. Entre otros, atrajo inmigrantes de la antigua y vecina Tarazona, cuya población judía y mozárabe se fue trasladando a las fértiles tierras de Tudela. La llegada de los judíos a Tudela debió ocurrir entre los años 905 y 926, quienes construyeron al menos una sinagoga, conocida como Sinagoga Mayor. Durante la dominación musulmana, los judíos tudelanos se extendieron por un extenso barrio denominado la Judería Vétula, formando la aljama más numerosa de Navarra. Tudela se convirtió, por tanto, en un crisol de gentes y culturas en la que, además de musulmanes, se mezclaron mozárabes y judíos. La población tudelana debio alcanzar durante los siglos X y XI cerca de 8.000 habitantes.
Tudela llegó a convertirse en capital de una taifa independiente, tras la caída del Califato omeya de Córdoba. Tras la muerte del rey hudí de Lérida, Suleiman ben Muhamad ben Hud, en 1046, el taifado de Zaragoza fue dividido entre sus hijos. La Taifa de Tudela fue reinada por Muhammad Hachib Mondzir, uno de sus hijos. Poco duró el taifado tudelano, aproximadamente unos 5 años (probablemente entre 1046 y 1051), pero, a pesar de su brevedad, hubo tiempo de acuñar moneda propia.
La "cultura andalusí" siguió siendo de marcada significación desde el siglo XI al XIII con figuras señeras tanto árabes como judías.
