En la parte más elevada del pueblo de Ujué podemos encontrar el templo fortificado dedicado a Santa Maria. La existencia de la población es anterior a la invasión morisca. Entre los siglos VIII y IX se estableció una fortificación para hacer frente al enemigo islámico. En el siglo X ya tenemos noticias de la existencia de un templo dedicado a Santa Maria. Según la leyenda, un pastor que perseguía una paloma (uxua en vasco) descubrió una imagen de la Virgen en una cueva.

El templo actual se empezó a edificar en el año 1089 por orden del rey Sancho Ramírez. De esta época sólo se conserva la cabecera, el primer tramo de las naves y el primer tramo de la torre que hay en el muro sur. Esta edificación tenía tres naves con planta basilical.

La cabecera la forman tres ábsides semicirculares. Se dividen verticalmente en tres partes gracias a dos contrafuertes de sección cuadrada. Bajo el tejado encontramos una cornisa con decoración en forma de ajedrezado jaqués y unos canecillos lisos. Por debajo de las ventanas encontramos una línea de imposta decorada también con ajedrezado jaqués. En cada uno de los tres ábsides encontramos una ventana de medio punto, decorada con una arquivolta que se apoya en columnas con los capiteles decorados con motivos vegetales o geométricos muy simples. Por encima de la arquivolta, a modo de guardapolvo, encontramos nuevamente decoraciones en forma de ajedrezado jaqués.

En el siglo XIV, Carlos II decidió reformar el templo. Se demolieron las naves, quedando en pie sólo la cabecera y el primer tramo. En el lugar de las tres naves románicas se edificó una única nave gótica. Este paso de tres naves a una única, también se produce en el monasterio de San Salvador de Leyre.

El ábside central tiene una serie de arcos ciegos, excepto el central dónde hay una ventana. Los arcos están apoyados en columnas con capiteles, la mayoría de ellos restaurados. Los originales tienen decoración con motivos vegetales y alguna figura humana. Una imposta separa los cilindros del ábside de las bóvedas. Los ábsides están separados de la gran nave gótica por los primeros tramos de las románicas. Arcos de medio punto, ligeramente peraltados, comunican la nave gótica con las románicas.

A los pies de la nave encontramos un coro de época gótica. Tres arcos apuntados separan este último tramo de la nave del resto. Sobre dos pilares y columnas adosadas descansan los nervios de las bóvedas de crucería sobre las que está edificado el coro.

Presidiendo el ábside principal podemos encontrar la talla románica de Nuestra Señora de Ujué del siglo XII. Posteriormente Carlos II la hizo recubrir de plata en el siglo XIV. El amor de este rey por el pueblo de Ujué y por su Virgen hizo que estuviera a punto de fundar una universidad y que su corazón se conserve en una arqueta en la cabecera del templo.

También fue obra de Carlos II la fortificación del templo y la construcción del camino de ronda que lo rodea. Es por este motivo que los ábsides románicos quedaron escondidos exteriormente por el muro del castillo. Actualmente se está restaurando el camino de ronda y por lo tanto no pude disfrutar de la maravillosa galería gótica. La torre campanario se completó y coronó con almenas.

De esta época también es la bella portalada gótica con esculturas bastante interesantes. La forman diez arquivoltas en gradación y apuntadas. La arquivolta exterior está decorada con flores y descansa sobre unas ménsulas decoradas con la escena de un caballero armado con su espada y escudo matando a un dragón alado y en otra un caballero matando a un dragón. El resto de las arquivoltas de la portalada se apoyan en unas molduras con decoraciones vegetales y escenas figuradas.

El tímpano se divide en dos registros. En el inferior podemos ver la representación de la Santa Cena, mientras que en el superior está representada la Epifanía del Señor con la Virgen mostrando el Niño a los Tres Reyes. También aparece un personaje en posición de oración.

En el muro norte de la nave también hay otra puerta que se abre a la galería gótica, En este caso la portalada también está formada por arquivoltas apuntadas en gradación y con una imposta decorada con motivos vegetales. En el centro de la primera arquivolta podemos encontrar un crismón.