Ante la falta de datos escritos, el único punto mas fiable es la constancia de la existencia de un núcleo de población pequeño, eminentemente árabe a finales del siglo VIII, que rompe con toda la tradición y cultura romano visigótica, y que empieza ejercer su dominio conquistador aunque de manera pacífica y tolerante. Cuando los árabes llegaron a este lugar debieron encontrar una aldea rústica y una posada. Todas estas construcciones rodeaban un pozo, y la existencia de agua fue determinante para el asentamiento de este grupo. Fueron estos árabes los que le dieron el nombre originario al pueblo de «Puebla» y por tener el agua cerca le añadieron «Del Aljibe», derivado de la palabra árabe «al-yibb», que quiere decir pozo. Este pueblo llegó a tener una agricultura próspera y un viñedo y olivar notable en el aspecto económico. Han sido encontrados restos de este pueblo árabe, como vasijas rotas, tejas, piedras de molino, amuletos, losas funerarias, y restos humanos enterrados bajo tierras de cultivo.  Según la tradición oral la fundación del pueblo de Sta. Mª de los Llanos data del siglo XIII, en el año 1290, cuando varios vecinos de» Puebla del Aljibe» se trasladaron al territorio llamado Los Llanos . muy cercanos entre si ,y paraje donde según la tradición un labrador encontró, arando  las tierras, una pequeña imagen de Santa Maria de cobre, y al considerarse el hecho milagroso se le hizo una pequeña capilla a la Virgen. Esta teoría se apoya en elementos de la iglesia del pueblo fechados en el siglo XIII.

Fueron  pasando los años y el lugar de culto se fue convirtiendo en morada de los antiguos vecinos de Puebla del aljibe. Es así como  poco a poco se fueron  asentando en Santa Maria al que se le añadió   de los Llanos por ser el nombre del paraje donde se apareció la Virgen.