Durante el periodo visigodo la ciudad creció en importancia, sobre todo desde el punto de vista religioso y cultural, llegando a ser sede episcopal. Complutum se convirtió además en un importante nudo de comunicaciones entre Toledo, la capital, y la Galia.

El obispo toledano Asturio o Astúrico encontró, en torno al 414, los restos de Justo y Pastor, en el supuesto lugar donde se produjo el martirio, el Campum Laudabile, casi un siglo después de que éste aconteciera, y trasladó las preciadas reliquias a la iglesia de la ciudad mientras se reconstruía una capilla dedicada a venerar a los Santos Niños. Este emplazamiento corresponde con la actual cripta de la Iglesia Catedral Magistral, alrededor de la cual fue creándose una nueva población, heredera de la Complutum romana.

Después de la conquista de Toledo en el año 719, Complutum se encuentra amenazada por los árabes que se apoderan del poblado complutense, construyendo una fortaleza en los cercanos cerros que la bordeaban por el sur, ampliada posteriormente con una ciudadela. Este emplazamiento se denomina Al-Qal´at Nahar (Castillo sobre el Henares), conocida como Alcalá la Vieja después de la Reconquista y que dio nombre a la futura ciudad.

Con el inicio de la etapa árabe, en el año 748, los cristianos, para evitar la profanación de los restos de los Santos Niños Justo y Pastor, trasladaron sus reliquias fuera del dominio musulmán al otro lado de los Pirineos; no regresarán a la Iglesia Magistral hasta el año 1568 gracias al rey Felipe II.

La definitiva conquista cristiana de Alcalá la lleva a cabo el arzobispo toledano Bernardo de Sédirac por encargo del rey Alfonso VI en el año 1118, pasando a ser Señorío del poderoso arzobispado de Toledo en 1129 y convirtiéndose, poco después, en una activa población gracias a su importante comercio y a la pacífica convivencia entre judíos, musulmanes y cristianos.