La catedral se empezó a construir en el año 1226 durante el reinado de Ferran III el Santo. Las obras se alargaron hasta el año 1493, momento en que se acabaron de construir las bóvedas de la nave central.  Este edificio se construyó, según dice la tradición, en el mismo solar dónde el primer arzobispo de Toledo, san Eugenio, hizo edificar un templo. Este, tal y como consta en una inscripción encontrada en el siglo XVI y que actualmente se conserva en el claustro, fue consagrado otra vez en el año 587 , tras haber realizado unas modificaciones.

Durante la invasión musulmana la sede episcopal se trasladó a la iglesia de Santa María de Alfizén, por que el templo visigodo fue transformado para alojar la mezquita mayor de Toledo, de la que todavía quedan algunos vestigios.

Alfonso VI conquistó la ciudad en 1085. Esto fue posible gracias a las capitulaciones, donde el monarca se comprometía a conservar y respetar los edificios de culto, las costumbres y la religión de la población. Al poco de la conquista el rey se ausentó de la ciudad, dejándola bajo la custodia de su esposa Constanza y de el abad del monasterio de Sahagún, convertido en arzobispo de Toledo, los cuales aprovecharon la ausencia del monarca para colocar un altar en la mezquita y una campana en el punto más alto del alminar. Este hecho estuvo a punto de provocar una rebelión y un alzamiento entre la población. Según la tradición, el rey, al enterarse de este hecho, dictó sentencia de muerte para todos los implicados y sólo la intercesión de Abu Walid, pudo aplacar la cólera del rey. En agradecimiento por este gesto, en el siglo XV se esculpió  una imagen de Abu Walid en uno de los pilares de la capilla mayor. De este modo la mezquita mayor fue convertida en catedral cristiana.

El 18 de diciembre de 1086 la nueva catedral se ponía bajo la advocación de Santa María. Se aprovechó este momento para adaptarla al culto cristiano, modificando la orientación de la capilla mayor. El edificio permaneció prácticamente intacto hasta el año 1222, cuando una bula papal autorizó la construcción de un nuevo templo, la primera piedra del cual se colocó en 1226.

El templo tiene cinco naves. Las dos más exteriores son más anchas que las otras dos laterales.

Inicialmente se proyectó el templo con tres naves, pero se modificó el proyecto inicial para que el templo ocupara toda la superficie de la antigua mezquita. Todas ellas están cubiertas con bóvedas de crucería y estrelladas.

El templo se empezó a construir por la cabecera, formada por una doble girola, que rodea la capilla mayor. 

Inicialmente ésta estaba dividida en dos partes independientes: la capilla de los Reyes Viejos y el presbiterio. El cardenal Cisneros consideraba que este último espacio no era digno de la catedral toledana y patrocinó la demolición de la capilla para ampliar el presbiterio y poder colocar el retablo gótico que él mismo había encargado.

Se trata de una de las últimas manifestaciones del arte gótico, al iniciarse en el año 1497 y se acabó siete años más tarde. Preside el retablo la imagen de la Virgen con el Niño, chapada en plata. En los espacios centrales se representan el Nacimiento de Jesús, la Ascensión y un Calvario. En el resto de escenas podemos ver diferentes momentos de la vida y Pasión de Cristo

Rodeaba la capilla mayor una "reja" de piedra ricamente decorada. La parte correspondiente junto al Evangelio fue destruida para ubicar el sepulcro del cardenal Mendoza.

En la cabecera todavía se conservan las ventanas del triforio y que originariamente recorrían todo el templo. El nivel inferior está formado por arcos lobulados, de clara tradición mudéjar, que descansan en parejas de columnas. Todavía durante la época gótica se suprimieron los triforios de las naves para hacer más grandes los ventanales.

La fachada principal, situada a los pies del templo, fue construida entre los años 1460 y 1468  . Tiene tres puertas, la central es conocida como la Puerta del Perdón.

En el parteluz se representó a Cristo bendiciendo a los fieles que buscan el perdón, al atravesar esta puerta. Le acompañan los doce apóstoles, agrupados de seis en seis, a ambos lados de la puerta. En el tímpano vemos a San  Ildefonso, que recibe la casulla de manos de Maria.

La puerta del lado izquierdo es conocida como la Puerta del Infierno o de las Palmas, por su decoración vegetal. La del lado derecho, en cambio, representa el Juicio Final. 

En el siglo XVIII fue necesario reforzar los muros del templo y modificar la fachada, dotándola de un aspecto más neoclásico. En la parte superior esculpieron una Santa Cena. 

Esta fachada tenía que estar flanqueada por dos torres. Se empezaron a edificar a finales del siglo XIV, pero la del lado derecho no se terminó. Sólo se construyó la parte equivalente a la altura de las naves y fue rematada con una cúpula en el siglo XVII y actualmente acoge la Capilla Mozárabe. La torre del lado izquierdo si que se terminó en el siglo XV, como lo demuestra su decoración, muy próxima al renacimiento.

En el brazo norte del transepto se abre la Puerta del Reloj, también conocida como Puerta de Fería, de Chapinería o de las Ollas. Es la más antigua de toda la catedral. En su tímpano se esculpieron tres frisos dónde se relatan varias escenas de la vida de Cristo. Podemos ver la Anunciación, la Natividad , la Epifanía, la matanza de los inocentes, la huida a Egipto, la circuncisión, Jesús entre los doctores, el bautismo en el Jordán y las bodas de Caná. Durante la reforma neoclásica se añadió un reloj, de aquí su nombre, que oculta parcialmente el rosetón gótico. El nombre de la portada de las Ollas viene dado por las grandes tinajas de vino de la escena de las bodas de Caná.

En el brazo sur del transepto encontramos la conocida como puerta de los Leones, debido a los seis leones que hay sobre las columnas dónde se sostiene la reja que protege la puerta. También se conoce con el nombre de Puerta de la Alegría por que en ella vemos la Asunción de Maria a los Cielos.

Es la más monumental de todas y se trata de uno de los mejores ejemplos escultóricos hispano-flamencos. Querubines y ángeles músicos, esculpidos en las arquivoltas, acompañan en Maria en su último viaje. Fue construida entre 1452 y 1465 si bien la mayoría de esculturas corresponden a la reforma del siglo XVIII, entre ellas la Virgen que preside el parteluz.

En el muro sur se abre también la Puerta Llana, denominada así por que para acceder al templo no hace falta subir ningún peldaño. Se realizó a finales del siglo XVIII y principios del XIX en estilo neoclásico, sustituyendo a una puerta anterior. Por su condición de estar a nivel de la calle, se utiliza para las procesiones de Corpus y Semana Santa.