La iglesia parroquial de Santa Maria es considerada por muchos como la capilla del palacio real. Si bien fue utilizada por los monarcas en algunas ocasiones, como por ejemplo el funeral de la reina Leonor, el castillo tenía su propia capilla, dedicada a San Jorge y este templo cumplía funciones de parroquia. A pesar de todo, junto al presbiterio podemos observar una ventana con el escudo de armas de Navarra que seguramente comunicaba el templo con el castillo.

La iglesia se empezó a edificar en el primer tercio del siglo XIII, ya en estilo gótico, si bien no se finalizó hasta bien entrado el siglo XIV. Consta de una sola nave rectangular formada por cuatro tramos desiguales. La nave está acabada en un ábside pentagonal. La bóveda que cubre la nave es de crucería reforzada por nervios y arcos fajones. Las claves de bóveda están decoradas, como también lo están los capiteles de los pilares que sustentan la bóveda. En los muros laterales podemos encontrar algunas capillas añadidas a lo largo de los siglos.

Lo que sin duda llama la atención del visitante es el gran retablo renacentista dedicado en Santa María, a quien podemos ver en una talla de principios del siglo XIV. Durante la restauración que se hizo en 2001 se pudo ver y fotografiar un conjunto pictórico que hay en el ábside. Se organiza en tres niveles a ambos lados de un gran ventanal. En el inferior hay cuatro apóstoles, en el siguiente algunos profetas y en el tercer piso es difícil poder identificar en quien pertenecen las imágenes. Se trata de un conjunto pintado en el siglo XIV. Quizás seria interesante poder trasladar el retablo de su ubicación actual y permitir al visitante contemplar también las pinturas, o quizás trasladar estas a otra ubicación o museo.

También se puede contemplar en el lado derecho de la cabecera una imagen del Cristo Crucificado del siglo XIV, conocida con el nombre del Cristo de la Buena Muerte.

El ábside pentagonal está reforzado con contrafuertes. En cada cierre de pared podemos encontrar unas esbeltas ventanas apuntadas con columnas adosadas y capiteles esculpidos. Una sencilla imposta divide el ábside horizontalmente. Se puede observar desde el patio de acceso al castillo-palacio. A su lado se puede observar la torre campanario. De planta cuadrada, destaca por su altura. En los dos últimos pisos se abren ventanas apuntadas con arquivoltas en gradación que sirven para alojar las campanas. Está coronada por una barandilla decorada y pináculos en las esquinas.

Pero sin duda lo más curioso de este templo es el atrio que hay ante la puerta de acceso al templo. Está formado por tres galerías de arcos apuntados y polilobulados . Tiene el aspecto de claustro sin cubrir. Se accede a él por un arco rebajado que tiene a ambos lados las imágenes de la reina Blanca y de la Virgen con el Niño, hoy en día sin cabeza.

La portalada está formada por ocho arquivoltas apuntadas y en gradación. Están ricamente decoradas con hojas de viña, roble, castaño, hiedra, ... Entre las hojas y colocadas de forma asimétrica, podemos ver las imágenes orantes de un rey y una reina, que se han identificado con Juana I de Navarra y Felipe el Hermoso. Las arquivoltas reposan en columnas con capiteles decorados. Los del lado izquierdo tienen motivos vegetales, mientras que los de la derecha están historiados. Sobre estos capiteles podemos encontrar unas imágenes de dimensiones desiguales. En el lado izquierdo están los tres Reyes, el rey Herodes, un ángel haciendo sonar una trompeta y otro arrodillado. En el lado derecho se ve a algunos pastores, si bien muy deteriorados, adorando a la Virgen y al Niño del tímpano.

En el centro del tímpano encontramos en la Virgen con el Niño Jesús sentado en su regazo en acción de bendecir, si bien ha perdido la cabeza y la mano. A alrededor se han dispuesto varias escenas de la infancia de Jesús. En el piso inferior encontramos la Anunciación, el Nacimiento de Cristo, la matanza de los inocentes y la fuga a Egipto. En el de arriba está la presentación de Jesús en el templo y el bautismo en el Jordán. El dintel está decorado con motivos vegetales, seres fantásticos y hombres cazando. Flanqueando la puerta encontramos ricas decoraciones de motivos heráldicos, animales reales y fantásticos, e imágenes del Antiguo y Nuevo Testamento.

Para acabar con el repaso a las esculturas de la fachada, hablaremos de los dos frisos de arcos apuntados trilobulados que se encuentran a ambos lados de la puerta. En su interior podemos ver las esculturas de los Apóstoles: seis a cada lado. Sobre los arcos hay esculpidos unos pináculos.

Corona la fachada un rosetón esculpido dentro de un gran arco apuntado formado por tres arquivoltas sustentadas en finas columnas de fuste liso y capiteles decorados.