El nombre de Lanaja es de origen árabe.
- En el siglo X, varias mesnadas de Abderramán III, vinieron en ayuda del rey de Zaragoza Abu Yahya, el mando de Nadja, antiguo esclavo que llegó a ser el primer general del Califato y murió en el fosos de Simancas en (939).
- Son importantes los restos de construcciones árabes como : la defensa, la atalaya denominada “Castillo de Montoro” y vivienda, son los restos del palacio-fortaleza llamada Mezquita, hoy la actual iglesia.
- A partir del siglo XVI, se puede suponer que no quedan restos materiales , por lo que se supone que se vería afectada por las distintas pestes de este siglo.
- Probablemente a finales del siglo XVII o principios del XVIII pasara una época de esplendor económico, pues de esa época son las dos ermitas más cercanas al pueblo, las de San Sebastián.
- Así llegamos a la mitad del siglo XIX en que sucede otra de las historias más conocidas en torno a Lanaja y a toda la Sierra de Alcubierre, la presencia del Bandido Cucaracha. Mariano Gavín, nacido en Alcubierre, casado con Jovita Amador, sin oficio conocido y muerto a los 37 años, el 28 de Febrero de 1.875, según el extracto de partidas de defunción de Lanaja en ese año.
