Aunque no existen datos documentales al respecto, es bastante probable que las primeras invasiones "bárbaras" destruyeran, al menos en parte, la ciudad complutense y que el material del que estaban hechas su vías y edificios romanos fueran reutilizados para la realización de nuevas construcciones.

De los estudios arqueológicos parece desprenderse que el antiguo y primer emplazamiento de Complutum dejó de tener actividad en torno al siglo V d. J.C. La población, no obstante, se había ido desplazando paulatinamente hacía el río ya en épocas anteriores.

Durante la monarquía visigótica, la ciudad no perdió su denominación romana y el hecho de hallarse cerca de Toledo (capital de la España visigoda) influyó notablemente en Complutum, que no dejó de ser un importante nudo de comunicaciones, aunque es evidente que se vio eclipsada por la capital del imperio arriano. Destaca su localización estratégica entre Toledo y las Galias, donde los visigodos tenían importantes intereses.

Compluto, sin duda, perteneció a la Galia Narbonense.

Pero el acontecimiento más importante que se produjo en este periodo es el descubrimiento por parte del obispo toledano Astúrico Anulino de los restos mortales de los santos Justo y Pastor (los Santos Niños). El hallazgo fue realizado en el supuesto lugar donde se produjo el martirio, el Campum Laudabile, casi un siglo después de que éste aconteciera.

La primera medida del mencionado obispo fue el levantamiento de una capilla en dicho lugar para proteger y venerar las preciadas reliquias. Este emplazamiento correspondería con el de la actual cripta de la iglesia Magistral.

Alrededor de esta primitiva capilla iría renaciendo una nueva población que recibiría el nombre de Neo-Compluto y que será la heredera de la ilustre Complutum romana.

Astúrico Anulino decidió, además, abdicar de la sede toledana para permanecer el resto de su vida en Alcalá, creando la sede episcopal complutense y convirtiéndose en su primer obispo. En esta nueva sede se sucederán hasta veintiséis obispos durante un periodo que abarcará incluso parte de la época de dominación musulmana. Se suele dar como fecha de extinción de la sede el año 1040, relativamente cercana a la conquista de Toledo por Alfonso VI (1085).

La presencia visigoda se constata en Alcalá de Henares en varios enclaves, siendo el más importante la necrópolis del Camino de los Afligidos, la cual ha permitido hacer un estudio detallado del ritual mortuorio de esta civilización.