Религиозное рвение новых властителей Толедо — королей Кастилии-заставляло их рьяно обращать мусульман в христианскую веру. По их приказу спешно перестраивались в церкви мечети и синагоги Толедо. Особый фанатизм проявляли королева Констанция, жена Альфонса VI, и ее духовник епископ Бернард. Королева без ведома короля, бывшего в то время в отсутствии, обратила главную мечеть в собор. Королева не посчиталась с тем, что Альфонс VI при взятии Толедо дал слово главному мулле Толедо Абуке Валиду не трогать мечеть. Королю пришлось иметь неприятное объяснение по этому поводу с Абукой Валидом, кончившееся, впрочем, мирно. За уступчивость в этом вопросе Абуке Валиду в соборе была поставлена статуя. Но мечеть, обращенная в собор, в свою очередь перестроенная из вестготской церкви Санта Мария дель Реаль, была невелика и не могла удовлетворить потребностей все увеличивающегося населения Толедо, в котором начинали преобладать испанцы. Король, высшие придворные и высшее духовенство мечтали украсить Толедо грандиозным собором в духе соборов европейских стран. Идеалом для них стали соборы Франции. Кастилия была в то время больше связана с Францией, чем с другими европейскими странами.
В 1227 году по повелению кастильского короля Фердинанда Святого мечеть, служившую собором, разрушили, и 14 августа того же года был заложен первый камень нового собора. Первоначально проект был поручен мастеру Мартинеру, затем главным руководителем работ был назначен Петрус Петри (1285), далее продолжали строительство Родриго Альфонсо (с 1389 г.) и Альфаро Гомес (между 1380–1440 гг.). Им принадлежит постройка северной башни, законченной Педро де Алалой. Собор по первоначальному плану предполагалось строить в строгом стиле классической готики по образцу северных французских соборов — в три нефа с деамбулаторием с пятью капеллами.
Но постройка собора продолжалась более двух столетий, и в процессе строительства он сильно расширялся и терял чистоту французских образцов, приобретая все более национальный характер. Начатый в XIII веке в готическом стиле, он заканчивался значительно позднее, в 1460 году, в эпоху господства в Испании искусства Ренессанса. Но это не нарушило цельности его художественного образа. Своеобразность испанского Ренессанса с его особой живописностью и богатством орнаментальных украшений гармонировала с декоративностью поздней готики. Кроме того, испанские строители никогда не оставляли своего увлечения мавританским искусством и привносили в архитектуру собора нарядность, столь чуждую стройной четкости французской готики.
Собор в Толедо является одним из грандиозных соборов средневековой Европы, он уступает по величине только соборам в Милане и Севилье. По роскоши же и торжественности убранства он превосходит все остальные соборы Европы. Доминируя над городом, выстроенный из великолепного серого гранита, он поражает импозантностью готических аркбутанов, пинаклями, башней и издали кажется родственным соборам Франции. Но, подойдя ближе (к сожалению, он очень загроможден тесно прижавшимися к нему домами), можно видеть, как чистота готического стиля французских соборов смело нарушена вкрапленными в него элементами то Ренессанса, то мудехаризма. Это сильно отличает его от соборов Франции, придавая ему внешне неповторимый характер. Кроме того, испанские архитекторы, не задумываясь, нарушали конструктивную идею собора, пристраивая к его основному ядру многочисленные ризницы, сакристии, клуатры разных стилей и разных объемов. Его северная, квадратная в плане, башня напоминает минарет (1380–1440). Это впечатление несколько рассеивается тем, что она увенчана как бы тиарой. Вместо южной башни поднимается купол мосарабской капеллы.
Чрезвычайно разнообразны по оформлению порталы собора. Главный портал выдержан в позднеготическом стиле, он носит название Пуэрта дель Пердон (портал Прощения). В тимпане главной двери портала помещен рельеф «Облачение святого Ильдефонса богоматерью», сюжет, очень распространенный в искусстве Толедо. Св. Ильдефонс считался покровителем города. На центральном столбе арки портала возвышается статуя Христа, на боковых сторонах — двенадцать апостолов. Над аркой проходит горизонтальной полосой рельеф с полукруглыми нишами, в которых помещены полуфигуры святых, чем нарушена идея готического портала с его неудержимым стремлением ввысь. Не по-готически выглядит и законченный в XVII веке фронтон, венчающий портал.