Magnífica dominando la plaza de la Inmaculada sobrecoge la dimensión y austeridad de su torre, enclavada en el tejido urbano de más rancio sabor. Los arbotantes del ábside nos anuncian desde las calles Santa Teresa de Jesús , Jorge Manrique la presencia del grandioso templo, no sin razón llamado "La Bella Desconocida" por la calidad y cantidad de tesoros que guarda en sus muros, desde el arte Visigodo al Renacimiento

Construida sobre antiguas edificaciones dedicadas al culto. Su origen lo encontramos en la Cripta Visigótica del siglo VII dedicada a San Antolín, donde posiblemente se encuentran las reliquias del santo, patrono de la ciudad. Se cuenta del Rey de Navarra que, pretendiendo cazar un jabalí, se adentró en una cueva y al arrojar su lanza contra él su brazo quedó paralizado; aquella cueva era la Cripta de San Antolín.

Del templo románico de tres naves y cubierta de madera, consagrado en 1219 por el obispo Tello Téllez quedan algunos vestigios, columnas y maderas policromadas. La nueva Catedral comienza su construcción en el siglo XIV y se prolonga durante dos siglos.
Declarada Monumento Nacional en 1929.
Exteriormente su austera torre de 30 metros de altura caracteriza la imagen del templo, que carece de fachada principal. La planta de tres naves, como trazada según modelo de la de Burgos, genera un interior que sorprende por su esbeltez, los detalles y la altura de su nave central. La verticalidad dominante sólo es rota por el triforio.
Bajo el coro, en el acceso a la cripta, destaca el trabajo plateresco de los bajorrelieves, con escenas del Rey Sancho y del martirio de Santo Toribio. La Cripta es un antiguo templo de dos naves: la primitiva visigoda del siglo VII y la segunda romanica del siglo VI ; una gran sala de bóveda de cañón con influencias prerrománicas.

Exteriormente desde la plaza de la Inmaculada presenta dos puertas: del Salvador o de los Novios, de corte ojival, con decoración heráldica y la de Santa María o del obispo con arquivoltas que se apoyan en un apostolado del siglo XVII, con ornamentación plateresca enmarcando los escudos de sus promotores.

A la plaza de Cervantes abre la puerta de San Juan o de los reyes, de trazado gótico y decoración plateresca y en la que se puede ver en hornacinas renacentistas imágenas de mártires, entre los que se encuentra San Antolín.
La puerta que comunica el templo con el hospital de San Antolín y San Bernabé data de 1762 y su nombre "puerta del Hospital" o "de los Canónigos" es el original del siglo XII.
A la plaza de San Antolín abre la puerta más reciente (1980), de corte neoclásico , completamente ajena al templo, firmada por Chueca Goitia.
El trascoro, de suntuoso plateresco es trabajo de Juan de Ruesga. Construido por el obispo Fonseca, su escudo aparece bajo el arco trilobulado de los Reyes Católicos.
Los laterales del coro son obra de Diego de Siloé. El Altar del Salvador rodeado de los cuatro evangelistas es trabajo de Felipe de Vigarny y el Altar del Cristo de las Batallas está firmado por Pedro Guadalupe.

El coro muestra la primera sillería realizada en nogal por Luis Centellas, ampliada por Pedro Guadalupe en el siglo XVI.
La capilla del Sagrario, obra de Sancho de Rojas con reja del XVI de Gaspar Rodríguez, presenta forma heptagonal y se cubre con ricas
nervaduras.
La Capilla Mayor con retablo de Pedro Guadalupe y Pedro Manso muestra esculturas de Felipe Vigarny y un San Antolín de Gregorio Fernández. Destacan Sepulcros como el de El Abad de Husillos o el Deán Enríquez.
Muchos son los personajes benefactores de este templo cuyas sepulturas son acogidas en capillas, a cambio de su enriquecimiento con objetos religiosos y retablos. Son las de Santa Lucía, San Fernando, de la Purísima, de San Miguel, San Sebastián o San Gregorio; ésta última con el famoso retablo del Milagro de San Cosme y San Damián de 1533 y atribuido a discípulos de Felipe de Vigarny.