El nombre de Móstoles aparece por primera vez con seguridad en un documento de 1144, que la cita como Turrem de Monsteles, «la torre de Mósteles». Pero bajo el casco antiguo hay huellas aún más antiguas, visigodas e islámicas.
Visigodos y andalusíes
La arqueología ha encontrado cerámica visigoda e islámica en distintos puntos del término, sobre todo en el centro urbano, donde se han localizado hasta siete viajes de agua subterráneos que probablemente datan de época islámica. La torre de la actual iglesia de la Asunción se levantó sobre la base de un antiguo alminar, posiblemente del siglo XI.
Un nombre de origen incierto
En los siglos XII y XIII los documentos escriben Monsteles o Mósteles; en 1208 el pueblo figura así en el deslinde entre las tierras de Segovia, Madrid y Toledo. El origen del topónimo es discutido: una hipótesis lo relaciona con un antiguo monasterio (monasterium) y otra con el nombre o apodo de algún repoblador que dio nombre al caserío.
La iglesia mudéjar
A partir del siglo XIII el núcleo se fue desplazando hacia la nueva iglesia parroquial, construida junto a aquella torre. Del templo mudéjar, levantado por albañiles musulmanes al servicio de los cristianos, se conservan el ábside semicircular y el presbiterio: es el edificio más antiguo de Móstoles.
Peste y aldeas perdidas
Las epidemias de peste negra del siglo XIV frenaron la repoblación y vaciaron varias aldeas del entorno, como Lucero, Aldea de Abad o Rodeviñas. Parte de sus vecinos se trasladó a Móstoles, que gracias a su buena situación en los caminos logró resistir y absorber sus tierras.