Edificada en 1140 sobre los restos de la antigua basílica prerrománica. A finales de siglo ya estaba construido casi todo el templo, excepto el cimborrio y la bóveda de la nave principal. Sirvió de modelo para muchas iglesias de la provincia, entre ellas la Colegiata de Santa María de Toro.

Se edificó a pocos metros del alcázar para que el recinto sagrado estuviera protegido adecuadamente. Su proximidad a la muralla defensiva hizo que se fortificara la torre campanario y el templo. Los tejados del transepto y de las naves laterales no son de teja, si no de piedra lisa a modo de camino de ronda, que se completa con unos pasillos que comunican las diferentes cubiertas.

La torre campanario destaca por su robustez. Tiene 45 metros de altura. Fue edificada a principios del siglo XIII a modo de castillo episcopal y su acceso se hace a través del cubierta norte.

Por encima del templo la torre se levanta cuatro pisos más. En el primero no hay ninguna apertura, al ser el más accesible. En el segundo, en cambio, encontramos una ventana de medio punto en cada uno de los muros. En el siguiente piso encontramos dos ventanas por pared y en el último tres. En estos dos últimos pisos es dónde se encuentran las campanas. Se cree que estaba coronada con almenas y un tejado a cuatro aguas, que al perder la función defensiva se eliminaron.

El templo tiene planta basilical con tres naves divididas en cuatro tramos. El transepto casi no sobresale de las naves laterales. Está cubierto con bóveda de cañón apuntada. En él se abrían tres ábsides semicirculares románicos, que fueron sustituidos en el siglo XV por uno gótico. 

Las naves laterales se construyeron con bóvedas de arista, mientras que la central, que fue la última en construirse, ya es de crucería con los arcos apuntados. Se cree que fueron las primeras bóvedas góticas de España. Como en algunos de los templos de la ciudad no se permite hacer fotografías del interior. Las que podéis ver han sido extraídas del Banco de Imágenes del Ministerio de Educación y Ciencia

En el punto dónde se cruzan el transepto y la nave principal encontramos una gran cúpula, que exteriormente se transforma en un espléndido cimborrio. Un cuerpo cilíndrico se apoya sobre pechinas y los arcos torales. En él se abren dieciséis ventanas de medio punto separadas por unas columnas dónde descansan los nervios de la cúpula. Posteriormente se cubrió con pinturas.

Del exterior destaca su forma de inspiración bizantina, coronada con un tejado a modo de escamas, de tradición francesa. Para aligerar el peso de la cúpula se construyeron cuatro torretas en las esquinas.

Otro de los elementos más interesantes de la catedral es la puerta del muro sur. Es conocida como la Puerta del Obispo. Es la única, de las tres que tenía el templo en época románica, que ha sobrevivido al paso de los siglos.

Está dividida en tres espacios mediante unas grandes columnas. En la parte central encontramos la portalada. Está formada por cuatro arquivoltas decoradas con rollos zamoranos. Estas se apoyan en columnas con capiteles esculpidos con motivos vegetales.

Sobre la puerta encontramos una arquería de arcos ciegos formados por una arquivolta, que se apoya en columnas. Sobre ellos encontramos un friso de arcos trilobulados con ménsulas troncopiramidales.

En el lado derecho de la puerta encontramos el conjunto escultórico de la Majestad. En él vemos a la Virgen Maria haciendo de trono al Niño Jesús, que ha perdido la cabeza con el paso de los años. A ambos lados encontramos dos ángeles. El conjunto está rodeado por un arco decorado con motivos vegetales.

Bajo este conjunto escultórico encontramos una cabeza esculpida y que en la actualidad está muy deteriorada. Según la tradición corresponde al moro Ome-Ya-bien-Moaviahque, que sometió a un feroz asedio la ciudad en el año 901 . El rey Alfonso III de Asturias acudió a socorrer la ciudad y un vez conseguida la victoria hizo colgar de las murallas las cabezas de los derrotados, para advertir de su suerte a todos los que volvieran a intentar conquistar la ciudad. Durante siglos los niños de la ciudad han tirado piedras contra la cabeza del moro. Quizás alguna piedra se desvió de su trayectoria y fue la culpable de que al Niño Jesús le falte la cabeza.

Al otro lado de la puerta encontramos otro grupo escultórico en el que están representados San Juan y  San Pedro dirigiéndose hacia la Virgen y el Niño, que están en el otro lado.

La puerta del lado norte quedó oculta en el siglo XVI cuando se construyó un nuevo pórtico de estilo herreriano. Son de la misma época la sacristía y el claustro. Este sustituyó al anterior románico, que se quemó accidentalmente durante una procesión en el año 1591.

La del lado oeste  se derruyó para edificar la capilla funeraria del Cardenal Meléndez Valdés.