Amrús Ibn Yusuf (+813) reconstruyó el viejo castillo de Tudela, por orden del emir de Córdoba, Alhakam I (796-822), en el monte de Santa Bárbara. En tiempos de Abderramán III. la madina (ciudad) ocupaba 24 hectáreas, con los ríos Queiles y Ebro como fosos naturales,

Bajo la alcazaba, el centro de la vida cotidiana era la mezquita mayor, o aljama: sala de oración, centro de reunión y escuela coránica, ágora y ciudadela a la vez para una población aproximada de 8.000 almas. Alrededor de la misma se abrían zocos o mercados, alcaicería (aduana) y oratorios privados.

En torno a la aljama mayor se asentaba la población musulmana, y no lejos la importante judería y los mozárabes, concentrados tal vez cerca de las iglesias de Santa María la Blanca y de la Magdalena.

Un sistema de torres atalayas o centinelas, apostadas en el valle del Ebro, reforzaba la madina, de la que es buen testigo la torre de Monreal, toda ojos a la derecha del río Queiles. Rodeada de una pequeña cerca, su espacio inferior estaba destinado al aljibe. El guerrillero décimonónico Espoz y Mina la hizo demoler por haber servido de fortín a los franceses. Su actual configuración poligonal -antes rectangular- se debe a su reconstrucción durante la última guerra carlista y a su restauración reciente.

Junto a ella perfuma aún la flor nueva de los romances viejos:

                                   ¡ Helo, helo, por do viene / el moro por la calzada
                                    caballero a la jineta / encima una yegua baya…!