Se sitúa junto al puente medieval, en el arranque de la Rúa Mayor que recorrían los peregrinos que desde Jaca se dirigían a Compostela. Es el templo más antiguo de Sangüesa, pues en origen se concibió como capilla del palacio edificado, a fines del XI, por mano del rey Sancho Ramírez y junto al puente. La construcción de la fábrica actual, que ha conocido diversas etapas, arranca con la fecha de 1131, cuando Alfonso I el Batallador la dona a la Orden de San Juan de Jerusalén. De esta época datarían los tres ábsides románicos de influencia jaquesa, de planta semicircular, con vanos también románicos y cubiertos por bóvedas de horno, que va además precedida de un tramo con bóveda de cañón en el caso del ábside central. En una segunda etapa, tal vez a principios del XIII y en estilo protogótico, se edificó el transepto y las tres naves cubiertas por bóvedas de crucería sobre pilares cruciformes, así como la gran portada del transepto, que da a la Rúa Mayor. Una última etapa, ya decididamente gótica, debe situarse en los siglos XIII-XIV, cuando se levanta la torre-cimborrio sobre el crucero, de planta octogonal y sobre trompas, con bóveda interior nervada. Lleva ventanales góticos y remate almenado culminado con chapitel piramidal. Esta fábrica medieval fue ampliada por dos capillas abiertas en el muro septentrional. La de San Miguel, antigua capilla real, gótica, con tres tramos de los que uno va con bóveda de cañón y los otros dos con bóvedas de crucería, y la capilla de los Remirez de Arellano, cuadrada y con bóveda estrellada del XVI.
Es sin duda la portada que da a la Calle Mayor el elemento más destacado de esta iglesia, no en vano es considerada la portada más rica del románico navarro y aún una de las mejores de la Península Ibérica. Se nota en ella la actuación de varios maestros, y algunos elementos hacen pensar que fue rearmada a posteriori, seguramente a principios del XIII, aprovechando elementos anteriores. El primero de los maestros que trabajaron aquí sería el llamado "Maestro de San Juan de la Peña", con sus característicos "ojos de mosca", figuras hieráticas, pliegues incisos muy simples y rostros cuadrados. A él debemos el apostolado de las dos galerías de arcos superiores. El otro maestro es algo más avanzado, probablemente procedía de Francia, y conocía al menos la escultura de la catedral de Chartres, a juzgar por el gran parecido que con aquella obra guardan las estatuas-columna de las jambas, obra de su taller. También obedecen a su mano el tímpano y el dintel.
La portada presenta abocinamiento salvado por cinco arquivoltas apuntadas, perfil que debe proceder de su montaje a principios del XIII, y que apean en las estatuas-columna ya citadas, que presentan un canon muy alargado. Las de la izquierda representan a las tres Marías, y la del centro, que figura a la Virgen, lleva en sus manos un libro en el que se lee: MARIA MATER DEI. LEODEGARIUS ME FECIT. Las figuras del lado de la Epístola son masculinas, y simbolizan a San Pedro, San Pablo y Judas, que a tal efecto aparece ahorcado y con la inscripción: JUDAS MERCATOR. Los capiteles, de buena talla, figuran la Anunciación-Visitación, la Presentación en el Templo, el Juicio de Salomón y otros motivos de raigambre vegetal.
Las arquivoltas llevan escultura en sentido longitudinal, donde se distinguen figuras tales como patriarcas, profetas, sirenas, animales y aves, acróbatas, representaciones de los pecados y de algunos oficios, etc. En el dintel hay una arquería que cobija al apostolado con la Virgen con el Niño en el centro. Va reforzado este cabezal por dos ménsulas labradas, respectivamente, con un carnero y con un monstruo, que porta un pez y una figura humana en la boca. En el tímpano se representa el Juicio Final, presidido por un Pantócrator que bendice y porta un libro en su mano, y que va rodeado de cuatro ángeles trompeteros, que anuncian el fin de los tiempos. A su derecha aparecen los bienaventurados, bien ordenados en dos registros, y a su izquierda los condenados, con las piernas temblorosas mientras esperan ser devorados por varios monstruos. También en este lado aparece el pesaje de las almas a cargo de San Miguel, iconografía de larga tradición que nos remontaría en última instancia al antiguo Egipto.
Sobre esta puerta hay un nuevo apostolado, repartido en dos arquerías de medio punto, en las que se incluyen también un Tetramorfos y un Cristo en Majestad, sedente, bendiciendo y con un libro en la mano. Las enjutas de este arco están abarrotadas de figuras en evidente desorden, donde seguramente se mezclan imágenes de diversas procedencias. Así, podemos ver reptiles, una mujer mordida por una serpiente, símbolo de la lujuria, un toro alado, un león alado y un águila, restos evidentes de un Tetramorfos, un caballero con una figura desnuda debajo, Adán y Eva, Caín matando a Abel, y varias figuras relacionadas con la saga nórdica de Sigurd, llegada probablemente a través del Camino de Santiago. De estas figuras, la más célebre y conocida es sin duda la del herrero Regin, mil veces reproducida. En los contrafuertes que enmarcan esta portada también hay varias figuras, entre las que distinguimos un León sobre figura desnuda, Cristo sedente, tres apóstoles y las Tres Marías ante el Sepulcro. En el tejaroz se encuentran canes que figuran animales y una figura en cuclillas.
Al interior preside el templo el retablo de Santa María, obra del siglo XVI, con traza recta con banco y dos cuerpos de tres calles. Entre la imaginería, los Cuatro Evangelistas, Anunciación, Visitación, Nacimiento, Epifanía, todas renacentistas, una Asunción del XVIII, y sobre todo la célebre Virgen de Rocamador, gótica del XIV, forrada de plata, imagen de gran trascendencia en la imaginería mariana del resto de Navarra. Cerca de este retablo, en los ábsides laterales, encontramos una escultura de San Blas, gótica del XV, y un Crucificado barroco del XVII.
En el lado del Evangelio del templo hay una pila bautismal de piedra, así como el retablo de la Piedad, barroco, situado en la capilla de los Arellano, y el retablo de la Virgen del Pilar que podemos admirar en la capilla de San Miguel, y que pertenece también al barroco. En el lado de la Epístola se encuentra el retablo de San Francisco Javier, obra moderna realizada en 1925. En la sacristía se custodian así mismo otras tallas, así como diversas obras de orfebrería.