En el año 1043, Tafalla es sitiada por los musulmanes. Con la ayuda del Rey García de Nájera se triunfa en esta contienda. El Rey concede el título de Nobles, Leales y Esforzados a los vecinos de Tafalla. De este triunfo nace el voto a la virgen de Ujué y así se inician las romerías.

Entre los grandes santuarios de Navarra, Ujué ocupa un lugar principal por su situación geográfica, la devoción ferviente de la gente de esta zona a la Virgen de Ujué, el arte e historia del santuario fortaleza y las características especiales de sus romerías.

Tafalla va a Ujué en romería penitencial dos veces al año, con modos y motivos diferentes. El domingo siguiente a San Marcos, 25 de abril, y aprincipios de mayo acude en masa junto a otros pueblos de vecinos.

El vestido, cantos, horarios, hacen de ella una de las más especiales y diferentes de Navarra. Los romeros se visten de túnica negra, cubren su rostro con un «capillo» igualmente negro y a veces arrastran cadenas llamadas «labradoras».

Salen de Tafalla a las cinco de la mañana en procesión, de uno en uno, y caminan sus veinte kilómetros hacia el santuario. Allí pasan el día y al anochecer vuelven con el mismo estilo para entrar en Tafalla al oscurecer. Cantan letrillas, himnos y letanías que tanto los tafalleses como los pueblos vecinos conservan desde siglos y todo ello adquiere un carácter ancestral y substancial a su fe. Es como asomarse a los viejos ritos de la Edad Media.

La noche del 30 de abril al 1 de mayo, hace su romería la Hermandad de los Doce Apóstoles de Ujué, desde el año 1607. Salen a las doce de la noche cuando el reloj parroquial marca las doce campanadas. Van y caminan, de uno en uno, en silencio total, con un farol de vela en su mano izquierda y un báculo en su derecha. Llegan al santuario a las cuatro de la mañana, tienen su misa y su frugal desayuno y a las seis reemprenden la marcha de vuelta, rezando rosarios y avemarías. Tras un fraternal almuerzo en el campo, a las doce en punto del mediodía, con el son de las mismas campanadas, entran en la Iglesia tras cruzar la ciudad.

La talla de la Virgen de Ujué es fechable hacia 1190 y forrada de plata en el XIV. A su lado descansa el corazón de Carlos II, rey navarro de la casa de Evreux y que fue quien levantó la nave gótica y rodeó la iglesia de pasos de ronda y torres almenadas, de las que sólo se conservan dos: la de los Cuatro Vientos y la de los Picos. Alrededor de esta iglesia-fortaleza, se desparrama el casco urbano, ejemplo excepcional de núcleo de origen medieval.