Se trata de una de las grandes iglesias parroquiales de Navarra. Ubicada en la plaza a la que da nombre, presenta un estilo ecléctico resultado de más de seis siglos de construcciones y reformas. Se intercalan en su fábrica todos los estilos que discurren desde el siglo XIII hasta el XVIII. Comienza la construcción en el siglo XIII; de este periodo protogótico se conservan los pilares cistercienses de las tres naves que discurren hasta el sotocoro. En el siglo XVI a la primitiva planta dividida en triple tramo se le añaden seis capillas laterales, un coro alto y otra capilla en el lado de la Epístola. Todas estas reformas de finales del siglo XVI otorgaron al conjunto un estilo plateresco. Pero en esta época las reformas no sólo afectaron al interior, sino que se agregaron al conjunto la torre a los pies y la portada del lado del Evangelio. Todas estas obras fueron realizadas por los hermanos Juan y Martín de Landerrain. Ya en la primera mitad del siglo XVIII se efectúa la remodelación barroca, que otorga a la parroquia el aspecto definitivo que hoy presenta. Fueron los maestros canteros Domingo Cascal y Domingo de Yturbe quienes en este periodo añadieron al conjunto las bóvedas de la nave central, de las capillas laterales, así como del crucero.
Presenta planta de cruz latina dividida en tres tramos prolongados hasta crucero y cabecera pentagonal. El alzado de la nave se realiza mediante grandes pilastras cajeadas de orden compuesto que discurren hasta un friso decorado con motivos vegetales. La cubierta se soluciona mediante bóvedas de medio cañón con lunetos para todos los tramos de la nave. En el crucero se alza una bóveda de media naranja. Toda la cubierta se realiza en época barroca por lo que adquiere una decoración interna de grandes yeserías y dorados. En la ornamentación de estos motivos intervinieron varios pintores como Juan de Mendoza, José Bravo o Pedro Antonio Rada. Decoran la parte alta con un rico repertorio iconográfico. Se representa diversas escenas con diferentes motivos vegetales y geométricos para volutas, pilastras, y cornisas. De gran relevancia, son las pinturas situadas en la zona del coro alto realizadas por el pintor José de Ordocia, discípulo de Santiago Zuazo. Fueron realizadas en el año 1761 y reflejan pasajes bíblicos.
Externamente la parroquia presenta un aspecto catedralicio, en el que sobresale la esbelta torre ubicada a los pies. Todo el perímetro de los muros se realiza con piedra de sillería, si bien se adivina en la parte baja de los mismos la parte correspondiente al periodo medieval. De entre todos los elementos que componen la estructura externa del destaca en cuanto a su clasicismo y belleza iconográfica la portada situada en el lado del Evangelio. Fue realizada en el último tercio del siglo XVI por los hermanos Landerrain. Se trata de una soberbia composición plateresca. Presenta un gran arco de medio punto inscrito entre dos pares de columnas de orden compuesto. Encima se monta un entablamento en el que aparecen grutescos y animales monstruosos. El conjunto se culmina con un medio punto abocinado mediante superposición de casetones. Destacan las esculturas de San Pedro y de San Pablo, así como dos magníficos tondos en los que aparecen representados dos profetas. Se trata de figuras muy expresivas, con detallados estudios anatómicos y en difíciles posiciones. La torre fue levantada en el último tercio del siglo XVI, también por los hermanos Landerrain, y constituye uno de los mejores ejemplos del renacimiento navarro. Su estructura se divide en cuatro cuerpos decrecientes. Los dos primeros son los más austeros y aparecen articulados mediante pilastras cajeadas. Ambos se separan por una línea de imposta. Se abre una ventana adintelada en el segundo cuerpo rematado por medio de un frontón recto. Destaca el último cuerpo de la torre en el que aparece una cúpula hexagonal decorada mediante motivos tardogóticos, con arbotantes y torrecillas.
El claustro enlaza con la iglesia por el lado de la Epístola. Constituye un buen ejemplo de claustro prerenacentista. Su construcción se atribuye a los hermanos Landerrain. En su estilo predominan las formas tardogóticas, con planta cuadrada en la que entre contrafuertes se localizan circo arcadas apuntadas decoradas mediante una variada ornamentación flamígera. Cada arquería cuenta con dobles arcos trilobulados con cuadrifolios en la parte superior. Se rematan las arcadas con círculos polilobulados. Los capiteles que soportan el peso de la bóveda de crucería de la galería aparecen decorados con motivos vegetales. Los nervios de la bóveda son de sección mixtilínea y en sus claves de las bóvedas se representan en relieve imágenes de los evangelistas, así como de animales.
El interior parroquial alberga una de las mejores colecciones de retablos barrocos de Navarra de los siglos XVII y XVIII. El retablo mayor fue realizado en la segunda mitad del siglo XVII por los maestros Viñaspre y Martín de Aranalde. En el camarín central se aloja la imagen gótica de la Virgen de Los Arcos, del siglo XIV. Presenta rigidez y estatismo, aunque el Niño aparece ya desplazado hacia la rodilla izquierda. El retablo configura una gran estructura cóncava adaptada a la cabecera.. Se divide en dos cuerpos de tres calles cada uno, que se articulan mediante sucesión de columnas de orden compuesto y fuste entorchado. Se remata el conjunto mediante un gran cascarón barroco aunque su estructura mantiene las características propias del estilo romanista. En las hornacinas de los dos cuerpos aparece un variado repertorio iconográfico con escenas bíblicas. Destacan las de la Asunción y de la Pasión. En muchas de las tallas y relieves se aprecia el estilo de Gregorio Fernández que aparece aquí reflejado por Juan Ángel Nagusia. Responden todavía a un estilo romanista que ha evolucionado hacia rasgos naturalistas.
Un magnífico retablo pictórico es el de la Visitación ubicado en el lado de la Epístola. Fue realizado en el siglo XVI. En su composición se percibe la influencia flamenca a través del estilo de Pedro Díaz de Oviedo. Su traza, gótica, se compone de un banco sobre el que se superpone un único cuerpo dividido en tres calles. En cada calle aparece un grupo escultórico que se complementa con unas pinturas de influencia naturalista propias del arte flamenco.
Entre otros retablos del siglo XVIII destacan los dedicados a San Juan Bautista y San Francisco Javier ambos obra de Juan Ángel Nagusia. El primero de ellos es de estilo barroco, con una factura mixtilínea en la que se dispone un cuerpo dividido en triple calle articulado mediante columnas de orden salomónico. El retablo de San Francisco Javier es de pequeño tamaño y aparece ubicado al igual que el de San Juan Bautista en el lado del Evangelio. En un único cuerpo dividido en tres calles se superponen columnas salomónicas que otorgan al conjunto un aspecto muy barroco y decorado. Se remata el conjunto mediante un ático de características similares y hornacina adintelada. Todo el conjunto aparece profusamente decorado mediante motivos vegetales.
Otros retablos del siglo XVIII son los dedicados a San Gregorio Ostiense, realizado por los maestros José Araya y Lucas de Mena, el del Corazón de Jesús, y el retablo de la Virgen del Rosario de Juan Ángel Nagusia.
En el coro destaca una magnífica sillería de estilo manierista realizada en 1577 por Martín Gumet. De gran vistosidad, se compone de 23 asientos. Cada tablero aparece separado por una pilastra acanalada y se remata con un arco de medio punto en los que aparecen relieves de santos y evangelistas. A Martín Gumet se debe también el facistol. Presenta éste estructura triangular entre leones; los frentes se decoran mediante tableros con relieves figurativos. En el coro se localiza un órgano rococó de la segunda mitad del siglo XVIII. La caja es obra del arquitecto Diego de Camporredondo en 1757. El órgano lo realizó en el mismo periodo el maestro organero de Lerín, Lucas de Tarazona. Se trata de una espectacular pieza compuesta como un retablo de tres cuerpos. Destaca el superior, articulado por cuatro columnas de orden compuesto.
En la sacristía sobresale una cajonería corrida realizada por Diego de Camporredondo. De traza mixtilínea, presenta un cuerpo decorado con motivos de rocalla. Los cajones también tienen numerosa ornamentación de rocalla. Las hornacinas albergan interesantes bultos redondos en los que se aprecia cierta rigidez y repetición del modelado. Concluye el inventario parroquial una notable colección de orfebrería con piezas que oscilan desde el siglo XVI al XIX. Entre las mismas destacan una campanilla de bronce de 1569, una crismera del siglo XVI, un cáliz de plata del siglo XVII y varias bandejas de plata del XIX.