Mesto je bilo domnevno naseljeno že v bronasti dobi. Rimski zgodovinar Livij (okoli 59 pr. n. št. – 17 n. št.) ga opisuje kot "urbs parva, sed loco munita" - majhno, naravno utrjeno mesto. Ko ga je leta 193 pr. n. št. osvojil rimski general Mark Fulvij Mobilio, je postal pomembna rimska kolonija in glavno mesto Karpentije.[1] V rimskem obdobju se je razvil v glavno trgovsko in upravno središče rimske province Carthaginensis. Po padcu Rimskega imperija je postal prestolnica Vizigotskega kraljestva, ki ga je ustanovil Liuvigild (ali Leovigild). Kraljestvo je propadlo po arabski osvojitvi Iberskega polotoka v letih 711 do 719.

V Kordovskem kalifatu je bil Toledo od leta 761 do 857 središče številnih uporov proti Arabcem.[2] Od leta 920 do 932 je mestu vladala dinastija Kasi, potem pa je mesto po dolgotrajnem obleganju osvojil Abd Al Rahman III..[3] Sledilo je obdobje, znano kot La Convivencia, se pravi obdobje sožitja muslimanov, kristjanov in Judov.

Arabci so Toledo preimenovali v Ṭulayṭulah. Don Izak Abrabanel, ugledna judovska osebnost iz 15. stoletja, ki je bil eden od kraljevih zaupnikov in priča izgona Judov leta 1492, je trdil, da so ga tako imenovali prvi judovski naseljenci, ki so se tja priselili v 5. stoletju pr. n. št.. Ime bi lahko bili sorodno s hebrejskim samostalnikom טלטול, ki pomeni (po)potovanje ali tavanje in simbolizira njihovo potovanje iz Jeruzalema. Prvotni poganski previvalci so mesto imenovali Pirisvale.[4][5] Po propadu Kordovskega kalifata je postal glavno mesto ene od najbogatejših taif v Al Andaluzu. Med prebivalci so prevladovali muladi. Zaradi svoje zemljepisne lege v osrednjem delu Iberskega polotoka je bil stalen cilj spopadov med muslimani in katoliškimi vladarji iz severne Španije. Leta 1085 ga je osvojil Alfonz VI. Kastiljski kot prvo večje mesto, ki je padlo v krščanske roke.

Alfonz VI. je osebno prevzel oblast v Toledu in začel pobirati davke v propadli Toledski taifi. Njeno ozemlje je priključil k svojemu združenemu kraljestvu Leon-Kastilja. Toledo je tudi po krščanski osvojitvi ostal glavno kulturno središče. Njegove arabske knjižnice niso izropali, ampak so v njej ustanovili prevajalsko središče, v katerem so islamski, judovski in krščanski učenjaki prevajali iz arabščine in hebrejščine v kastiljščino, kastiljski učenjaki pa iz kastiljščine v latinščino. Dolgo pozabljeno znanje se je začelo znova širiti v krščansko Evropo.

V 16. stoletju je bil Toledo nekaj časa prestolnice Kastilje. Dvor se je zatem preselil v Valladolid in nato v Madrid. Njegov pomen je zato upadel, dokler ni v poznem 20. stoletju postal glavno mesto avtonomne regije Kastilja-La Manča. Gospodarsko nazadovanje je po drugi strani pripomoglo k ohranitvi njegove kulturne in arhitekturne dediščine, zaradi katere ga vsako leto obišče mnogo turistov.