La caída de la Marca Media a finales del siglo XI y la posterior conquista por parte de las tropas castellanas lideradas por Alfonso VI de un amplio territorio situado entre la sierra castellana y la ribera del Tajo, posibilitó la ocupación en el año 1085 de emblemáticas ciudades-fortalezas (Toledo, Madrid) hasta entonces en poder del Islam aunque en decenios posteriores pudieron ser recuperados de forma temporal por los árabes. Una vez consolidada la frontera al sur del Tajo, a lo largo del siglo XIII, los reyes de Castilla se vieron obligados a conceder un cierto protagonismo a las ciudades en el proceso de repoblación, al ser los únicos dotados con los recursos suficientes para organizar el doblamiento de las tierras recién conquistadas. Las ciudades y sus respectivos entornos agrarios se constituyeron como Comunidades de Villa y Tierra.
En el año 1294 el rey Sancho IV de Castilla entrega el señorío, llamado entonces Torrejón de Sebastián Domingo, a Don Gonzalo Ruiz, alcalde de Toledo y señor de la Villa de Orgaz, quien posteriormente lo entregaría como parte de la dote de una de sus hijas que esposó a Lope Velasco, dándole la denominación actual al municipio. Alfonso XI, ya en el 1293, confirma la donación del señorío a Lope Velasco.
A lo largo del siglo XIII, los nuevos pobladores provenientes principalmente del Valle del Duero, procedieron bajo la tutela y la dirección del concejo de Madrid, y en virtud de sus fueros otorgados en 1202, a asentarse en territorios limítrofes tales como Getafe, Cubas, Griñón o Torrejón de Velasco.
En 1432, el señorío pertenecía a Gutiérrez Gómez de Toledo, obispo de Palencia y tío del primer duque de Alba, sucediendo así a su madre Doña Leonor Fernández de Ayala, dama perteneciente a un prestigioso linaje toledano. Durante esta época de anarquía feudal, Gutiérrez Gómez se convierte en arzobispo de Toledo y su enemistad con el rey Juan II, debido a la ocupación del obispado más codiciado de Castilla, desencadena un conflicto militar que se salda con la derrota del primero en la batalla de Olmedo (1445) y la cesión del señorío al conde de Plasencia. Posteriormente, los derechos pasan a Enrique IV, sucesor de Juan II y después a Alvar Gómez de Ciudad Real, secretario del consejo real. Con los Arias Dávila la Villa de Torrejón comenzó a gozar de numerosos privilegios reales, como la celebración de un mercado semanal libre de tributos y de una feria ganadera en primavera, lo que condujo a una etapa de prosperidad económica, truncada en parte por la revolución comunera de 1522 contra Juan Arias Dávila, que se saldó con daños en el castillo, saqueos en las casas y un gran incendio ocasionando la pérdida de archivos, fábricas y comercios. Su apoyo también al alzamiento militar contra los comuneros en el Alcázar de Madrid provocó que el emperador Carlos V en 1523 estableciera para el linaje Arias Dávila el título de Conde de Puñonrostro y el castillo como capital del estado condal y residencia permanente de los señores.