Construida sobre el solar de unas termas romanas del siglo II, que fueron convertidas en palacio real por Ordoño II en el siglo X. Este palacio se donó luego a la Iglesia para erigir una basílica que el obispo don Pelayo reedificó de 1065 a 1073. En los primeros años del siglo XIII hubo necesidad de transformar el templo que resultaba insuficiente. En tiempos del obispo Manrique de Lara, el maestro Enrique, que ya había trabajado en la catedral de Burgos, emprendió las obras: hay constancia de que en 1258 se estaba edificando la cabecera de lo que habría de ser un perfecto modelo del arte gótico, que quedaría concluido en el mismo siglo por el maestro Juan Pérez.
La gran fachada occidental está formada por dos torres, la de las Campanas y la del Reloj, que flanquean el pórtico abocinado con rica decoración escultórica, en el que trabajaron el maestro Enrique, Juan Pérez y Pedro Cibriánez.
Lo componen cinco arcadas desiguales que preceden a las tres portadas; la central está presidida desde el parteluz por una copia de la imagen de la Virgen Blanca, cuyo original se encuentra en el interior del templo.
A cada lado de la puerta hay tres esculturas de apóstoles, sobre los que cabalgan las tres arquivoltas decoradas con figuras que representan el Juicio Final, tema que ocupa la parte inferior del tímpano de la portada, y sobre el que se ve al Salvador como Juez Universal, flanqueado por ángeles con símbolos de la Pasión, la Virgen y San Juan; las puertas de madera son del siglo XVI.
Junto a la torre de las Campanas se encuentra la portada de San Juan, también flanqueado por esculturas de santos, profetas y reyes, y en cuyo tímpano, apoyado sobre un dintel adornado con ángeles músicos, se desarrollan varias escenas evangélicas; también las puertas son renacentistas.
El hastial central está adornado con el espléndido rosetón de la Gloria, que destaca sobre los ventanales del triforio.
La fachada meridional es la más suntuosa de las dos laterales. Se compone de un triple pórtico; la portada central es la llamada de San Froilán, la de la derecha todavía conserva restos de la policromía original; las tres arquivoltas están decoradas con ángeles y el tímpano con relieves alusivos posiblemente a la historia del santo obispo; la otra portada lateral, llamada de la Muerte, aparece ornamentada con castillos, leones y decoración vegetal.

El ábside se apoya sobre la parte oriental de la antigua muralla y forma una auténtica sinfonía de ventanales, contrafuertes, arbotantes y pináculos. La planta de la catedral, parecida a la francesa de Reims, es de cruz latina, con tres naves separadas por finos y altos pilares, cubierto todo con bóvedas de crucería.

La colección de vidrieras es única y alcanza el número de de 737, con una superficie de más de 1.765 metros cuadrados. Hay vidrieras de los siglos XIII al XX, algunas de ellas según cartones del pintor Nicolás Francés, del siglo XV.
El retablo mayor actual es un pequeño resto del que en la primera mitad del siglo XV realizara Nicolás Francés, uno de los mejores representantes del estilo gótico internacional en Castilla. Desde 1724 hasta la restauración del templo, a fines del siglo XIX, ocupó su lugar un gran retablo barroco realizado por Simón Gavilán Tomé y su sobrino Narciso Tomé, que luego fue trasladado al convento de san Francisco. En el altar mayor se encuentra la doble arca de San Froilán, de madera chapada en plata, con bellos relieves renacentistas, que realizó en 1519 el orfebre Enrique de Arfe.

El coro es uno de los más antiguos de España; fue ejecutado en la segunda mitad del siglo XV por el flamenco Jusquín, si bien la talla de las sillas de nogal corrió a cargo del imagienero Juan de Malinas y de Diego Copin de Holanda. En los ángulos de la sillería lata y en los de la baja se añadieron, en el siglo XVI, unos tableros de Bautista Vázquez. Las puertas de los corillos y los cuatro tableros de la parte delantera fueron añadidos en el siglo XVIII por Narciso Tomé. Está dividido en dos coros; el del obispo, en el lado de la epístola, y el del Rey, en el del evangelio; el coro bajo muestra escenas del Antiguo Testamento y el alto está ocupado en su mayor parte por santos. El trascoro fue realizado en el siglo XVI por Esteban jordán, a quien pertenecen los relieves que lo adornan; el hermoso crucifijo de remate es obra de Bautista Vázquez.

Las capillas guardan buenas piezas artísticas de diferentes épocas y estilos: entre ellas cabe citar la de San Francisco, con una magnífica pila bautismal renacentista de Juan de Badajoz; la del Dado, con pinturas de Nicolás Francés y una buena talla de San Sebastián, de Bautista Vázquez; la Libería o capilla de Santiago, buen ejemplo del gótico florido, construida por Juan de Badajoz en 1492 y decorada con vidrieras de Diego de Santillana en 1507; la de la Virgen del Camino, con sepulcros góticos y un lienzo del Salvador, de Diego Valentín Díaz, frente a la cual se encuentra el rico sepulcro del rey Ordoño II, de fines del siglo XII y ampliado en el XV. En el crucero hay un gran retablo de fines del siglo XV que procede de Quintanilla del Olmo (Zamora). En el oratorio se conserva un retablo de Churriguera, fechado en 1729. El vestíbulo que da paso al claustro está decorado con esculturas románicas pertenecientes al primitivo templo.

El claustro tiene dos partes, una gótica del siglo XIII y otra renacentista realizada en 1540 por Juan de Badajoz. Se accede a él a través de una portada gótica con puertas de nogal decoradas con relieves de gran calidad, como el de la anunciación que sido atribuido a Juan de Juni. En el claustro hay varias pinturas murales al temple realizadas por Nicolás Francés, numerosos sepulcros góticos y un altar plateresco que ejecutó Juan de Badajoz. Una gran escalera plateresca del mismo artista conduce a la sala capitular.

El Museo Catedralicio, instalado en las dependencias capitulares con acceso desde el claustro, atesora una buena colección artística integrada por una notable escultura gótica del rey Ordoño II; varios ricos códices, entre los que sobresalen el antifoniario mozárabe del siglo XI y la Biblia y tablas y esculturas de varios estilos. El archivo es uno de los más ricos de España en Códices y documentos de todas clases.