Первые люди поселились здесь ещё во времена неолита, потом в этой местности какое-то время жили племена кельтов, а в I в. до н. э. римляне основали здесь город Комплутум (лат.Complutum), от которого происходит уменьшительное название Алькалы — Комплутенция. По приказу императора Диоклетиана в 306 году здесь казнили двух мальчиков-христиан, Хусто и Пастора, после чего в город потянулись паломники, спустя столетие архиепископ Толедоканонизировалмучеников, почитаемых в Испании по сей день. После римлян окрестные земли принадлежали визиготам.
С 711 года местность попала под власть арабов, которые возвели на высоком холме чуть в стороне от римского поселения крепость, названную «al-qalat» — что в переводе означает «замок, крепость», но поскольку городков, содержащих в названии слово «алькала», в Испании немало, к имени этого добавляют «де Энарес» (название местной реки).
3 мая 1118 года город был отбит войсками архиепископа Толедо, и новые жители предпочли обосноваться на римском месте, оставив замок разрушаться. Город развивался в основном благодаря оживленному рынку и выгодному положению: по этой дороге короли Кастилии путешествовали на юг. 20 мая 1293 года король Кастилии Санчо IV подписал указ об открытии в городе Estudios Generales, переданных в ведение архиепископа и получивших благословение Папы Римского. Эти Генеральные штудии послужили фундаментом будущего университета, основанного в 1496 году (по некоторым источникам — в 1499) кардиналом Сиснеросом.
В XVIII—XIX веках город пришёл в упадок, университет в 1836 году перенесли в столицу (сегодня это Мадридский университет Комплутенсе), монастыри вокруг распродали землю, и городок превратился в спальный пригород Мадрида.
Достопримечательности
Центр города внесён в список всемирного наследия ЮНЕСКО. К числу основных достопримечательностей можно причислить соборную церковь, заложенную в 1136 году и возведённую в готическом стиле (она сильно пострадала во время гражданской войны XX века), и архиепископскую резиденцию, в которой ныне хранятся архивы инквизиции.
В церкви коллегиума Сан-Ильдефонсо находилась сначала, перенесённая потом в Мадрид, гробница «великого кардинала» Хименеса де Сиснеросa, который основал здесь в 1499—1509 годах пользовавшийся некогда всемирною известностью университет, закрытый в 1836 году и затем вместе с библиотекой переведенный в Мадрид.