Una impresionante escalinata nos transporta hasta la singular portada de este monumento, poseedor del título de iglesia mayor de la ciudad, calificativo que le fue otorgado en el año de 1256. Desde su altura se visiona una gran parte de la ciudad.
Dependiente de S. Juan , como las otras iglesias, se construyo en el ultimo cuarto del s. XII y principios del XIII, combinandose los estilos romanicos y cisterciense. Consta de tres naves precedidas por otros absides semicirculares y dos airosas torres prismaticas a los pies. La portada septentrional es de archivoltas apuntadas (la interior es angrelada) y muy abocinada, con suntuosa decoracion escultorica que conserva parte de su policromia original. A esta iglesia esta asociada la tradicion mas cara a los estelleses. Segun la misma, hacma 1.270 murio a consecuencia de las penalidades del camino un humilde peregrino griego, que fue enterrado en este claustro. Unos resplandores misteriosos llamaron la atencion sobre su tumba. Hechas las oportunas averiguaciones, se descubrio que, en realidad, se trataba del obispo Patras, portador de una gran reliquia de S.Andres, que llevaba como donacion a Santiago. Desde entonces se venera esta reliquia en S.Pedro de la Rúa, en un gran relicario de plata y S Andres se convirtio en patrón de Estella
La fachada, acogida anteriormente bajo pórtico, data de mediados del siglo XIII. Presenta grandes similitudes con las portadas de las cercanas iglesias de San Román de Cirauqui, y Santiago en Puente la Reina. Por sus capiteles y arquivoltas, discurre en delicado encaje una rica decoración de carácter vegetal, geométrico y figurativo. Sobre las jambas de la puerta, encontramos una rica figuración de origen clásico y de tipo escatológico, con sirena, centauro, arpías y grifos.
El interior del edificio presenta formas constructivas que se originaron en el último cuarto del siglo XII. De este período se conserva la cabecera del templo. Del siglo XIII son las naves, y del XV, el monumental ventanal de tracería gótica, situado en el muro norte de la iglesia, en su primer cuerpo y dentro de su colosal torre. De los siglos XVI y XVII son las cubiertas de las naves. El interior, de serena belleza, sobre todo en su cabecera, cobija diversas obras entre las que destaca el retablo de la Virgen del Rosario, de la primera mitad del siglo XVII. En su hornacina central se aloja una imagen de la Virgen de la O, obra datable en el siglo XIV. Con formas barrocas se construye y adorna la capilla de San Andrés, patrono de la ciudad, cuya fecha de edificación se inicia en 1706. El retablo, acogido entre sus paredes, es una fábrica de estilo rococó, cuya construcción se realizó a finales del siglo XVIII. Es de destacar el retablo del Crucificado, obra del siglo XVII, que ampara en su hornacina principal, una talla del Cristo en la cruz de carácter románico al que podemos fechar en el siglo XIII. En el Presbiterio se conserva la imagen de la Virgen de Belén, talla realizada a finales del siglo XIII y que procede de la cercana iglesia del Santo Sepulcro. Otros retablos, son el de San Nicolás y el de la Santísima Trinidad, cuya fábrica nos traslada al siglo XVII.A los píes de la iglesia, en el sotocoro y bajo el gran ventanal de la torre se guarda una bella sillería barroca y una pila bautismal del siglo XII,l único objeto litúrgico del primitivo edificio. Sobre las viejas paredes cuelgan lienzos de desigual calidad técnica, pero todos ellos atribuibles al siglo XVII.
Quizas lo mas interesante de este templo sea su claustro, del que se conservan dos alas del s. XIII (las otras dos quedaron destruidas en 1.572 al demoler el castillo bajo el que se asienta), con arcos de medio punto sobre columnas pareadas con capiteles unicos de decoracion historiada, de influencia silense. Fue utilizado en la Edad Media como cementerio de peregrinos. Cuenta con capiteles decorados con temas vegetales y animales, así como diferentes escenas bíblicas. Un capitel doble recibe cuatro columnas torsas similares a las del Monasterio de Santo Domingo de Silos (Burgos).