Nel periodo romano la città si chiamava Complutum e si trovava a pochi chilometri dell'Alcalá de Henares moderna. Fu una delle città più importanti della Penisola Iberica, come lo dimsotrano i resti che ancora oggi conserva. Furono 400 anni di splendore sotto la dominazione dell’Impero, soprattutto grazie all’utilizzo del fiume Henares, delle nuove vie di comunicazione e delle risorse agricole. Dopo i Romani, arrivarono gli Arabi, che nell’850 costruirono il castello di A-Qalàt en Nahar, da cui deriva il nome di Alcalá.
La sua importanza come roccaforte della valle del Tajo durante la Riconquista Cristiana contribuì a dotare la città di nuovi edifici e di una muraglia. Al suo interno convivevano ebrei, musulmani e cristiani, e ogni gruppo disponeva della propria zona di influenza nella fortificazione. Nel XIII secolo, Alcalá divenne una signoria degli arcivescovi di Toledo, che costruirono il Palazzo Arcivescovile e fecero assumere alla città una grande importanza con la presenza di una forte attività economica.
Nel 1293, Sancho IV concedette a Alcalá il privilegio di creare uno “Studio di Scuole Generali”, riconoscendogli la condizione di città universitaria. Ma il periodo di massimo splendore giunse con il Cardinale Cisneros che nel 1499 fondò l’Università Complutense. Pur se gli insegnamenti ebbero inizialmente un marcato orientamento religioso, rivolti soprattutto alla teologia e all’educazione ecclesiastica, l’Università ben presto sviluppò gli studi umanistici, la giurisprudenza e la letteratura grazie a personaggi del calibro di Quevedo, San Ignacio de Loyola o Santo Tomás de Villanueva. Tuttavia, nel 1836, le facoltà passarono a Madrid. Dopo un periodo di declino, a metà del XX secolo la vita universitaria della città tornò all’antico splendore con l’industrializzazione.