La comunidad mozárabe subsistió hasta el siglo XI en que se trasladó a la vecina Guadalajara.
El rey Alfonso VI, tras conquista de Toledo en el año 1085, encargará al arzobispo toledano don Bernardo la toma de Alcalá. Éste se apoderará de la antigua Complutum, pero no de la fortaleza a la que somete a asedio infructuosamente. Efectivamente, el poblado árabe de la ribera caerá en el 1088. Se dice que el castillo fue tomado temporalmente en el año 1095, pero que volvió a caer en manos musulmanas en el 1098.
Su conquista definitiva no se producirá hasta el 1118, por obra del mismo don Bernardo; la rendición se consiguió tras prolongado y encarnizado asedio, el 3 de mayo. Este hecho se ha relacionado con el llamado milagro de la "Vera Cruz", que socorrería a los cristianos y les ayudaría a vencer en la batalla.
A raíz de la toma del castillo, se establecería en él y sus arrabales una población cristiana que se mezcló con los mudéjares que se quedaron. La población se iría extendiendo e incluso ocupó el otro lado del río. Éste núcleo sería conocido como Alcalá la Vieja.
A la vez y lentamente, se inicia la repoblación alrededor de la recién creada parroquia de los Santos Justos y Pastor, situada en el lugar donde Astúrico alzara la primitiva ermita de los Santos Niños, que con el tiempo desde el S.XIVpasará a denominarse Alcalá La Nueva o Alcalá de Henares, hasta entonces Burgo de Santiuste.
Pocos restos han sobrevivido de esta época. Cabe destacar los de la antigua fortaleza, situados entre una ladera del Cerro Ecce Homo y la orilla izquierda del Henares, a la altura de la Ermita del la Virgen del Val y los numerosos fragmentos de cerámica árabe encontrados en la zona que debieron ocupar los arrabales que se hallaban fuera del recinto amurallado.