В III веке город стал центром христианского округа: легенда сделала из Леокадии мученицу эпохи императора Диоклетиана, в 300 году епископ Меланктий присутствовал на Элвирском соборе, а в 400 году на собор в Толедо прибыли девятнадцать епископов.
Во второй половине V века многочисленные вестготы обосновались в центре Испании, между Эбро и Тахо, в районе, где находился небольшой город Толедо (его площадь внутри стен составляла 5 гектаров). Доминирование вестготов в этом регионе, без сомнения, объясняло их интерес к нему после их отступления на полуостров. В 546 году город стал «резиденцией королей» (sedes regia). Но лишь при короле Атанагильде, умершем в 568 году в Толедо, город стал столицей королевства, «королевским городом» (urbs regia).
Вестготская столица
Расположенный в географическом центре полуострова, Толедо занимает стратегическое положение. В период Средневековья Толедо был связан с вестготами, то есть с их корнями в истории, с их прошлой славой, потерянной, а затем восстановленной.
Короли и епископы VII века сделали город настоящей столицей, городом, не имевшим себе равных в Испании. Многочисленные римские постройки были сохранены, так же как и городская стена. В городе были построены собор и многочисленные церкви. При отсутствии археологических раскопок точное местонахождение этих памятников вестготского зодчества можно только предполагать.
Административная столица королевства, город Толедо в VII веке принимал многочисленные ассамблеи дворян и епископов, которые избирали короля. Королевский дворец существовал здесь уже в конце VI века. Королевский город Толедо стал также столицей испанской церкви. Вестготские короли сделали из епископа столицы главу церкви в королевстве, который мог приказывать всем остальным епископам Испании, которые назначались королем. Политическая и религиозная столица, Толедо был также культурным и художественным центром.
Резиденция метрополита, действовавшего в качестве патриарха, Толедо стал прибежищем для крупной еврейской общины. Притеснения евреев, начатые королем Сисебутом (612—621) и продолженные королем Эгикой (687—702), без сомнения, дезорганизовали эту общину, но не положили конец присутствию евреев в городе.
В 712 году Толедо был взят мусульманами, а королевская казна расхищена. Среди ее сокровищ, согласно легенде, был «стол царя Соломона», изготовленный в Иерусалиме из огромного изумруда, украшенного золотом, серебром и драгоценными камнями, который вестготы привезли из Рима в 410 году, и который Тарик отправил халифу Дамасскому в качестве доказательства завоевания Испании.
Мусульманский город
Новые правители Испании избрали своей столицей Кордову, но Толедо (под названием Тулайтула) стал городом королей (Medina al-Muluk). Христиане, евреи и мусульмане жили здесь вместе почти четыре века под властью мусульманских губернаторов или эмиров.
Христиан в Толедо оставалось много, и, согласно обычаям, они имели право сохранить свои законы и религию, свои церкви, свое духовенство, своих судей и административные органы. Со временем число христиан уменьшалось, но все равно как минимум семь церквей оставалось открытыми к концу XI века. Еврейская община занимала, начиная с IX века, отдельный район, расположенный на западе города, он был опоясан стеной в 820 году. Немногочисленные первоначально, мусульмане стали преобладать в городе в IX веке, в значительной степени это было связано с начавшейся в этот период исламизацией.
Толедо с середины VIII века отличался независимым духом и способностью противостоять власти Кордовы: однако в 806 году, чтобы подавить восстание в городе, губернатор Талаверы казнил всех дворян Толедо, их было примерно 700 человек. Абд аль-Рахман III осадил город, и тот сдался 1 августа 932 года. Халиф приказал восстановить все то, что он разрушил, возвел замки и крепость, и город стал процветать под эгидой губернаторов, назначавшихся в Кордове. Население города, составлявшее примерно 20—30 тысяч жителей, жило сельским хозяйством и ремеслом. После падения халифата в 1031 году власть в Толедо перешла к берберскому семейству Бану Ди л-Нунов. Исмаил ибн Ди л-Нун аль-Зафирили «Триумфатор» (1032—1043) и особенно его сын Яхия ибн Исмаил аль-Мамун сделали из Толедо столицу владений, простиравшихся от Валенсии до Кордовы, мир с северными соседями-христианами был гарантирован выплатами значительных податей (parias). Аль-Мамун построил себе в верхней части города великолепный дворец, окружил себя учеными и поэтами, математиками и астрономами, покровительствовал искусству и литературе.