En el año 711, la rápida destrucción del reino godo debido a luchas internas propició la entrada en la península de los musulmanes del norte de Africa. Muza avanza por la Vía de la Plata desde Itálica, el 30 de junio del año 713 capitula Mérida ante sus huestes. Su hijo y primer walí de Al-Ándalus, Abd-el-Aziz somete al año siguiente, 714, la fortaleza de Magacela. Sierra de Gata quedó definitivamente en manos musulmanas tras la conquista de Coria en el año 750.

El sometimiento de las tierras extremeñas a los walies y a los emires de Córdoba, no implicó una total pacificación de la región. El establecimiento en ellas de bereberes, y la pervivencia hasta el siglo X de importantes núcleos cristianos, explican la sucesión de enfrentamientos con los clanes árabes de Córdoba. La participación de Mérida en sublevaciones contra el poder central andalusí, se repite durante los siglos VIII y IX. Lo que no sabemos es si los habitantes de la aldea de Cilleros emigraron hacia el norte ante la invasión o si, por el contrario, permanecieron en la zona, beneficiándose con ello de los arrendamientos de las tierras a los bereberes, a quienes tocó en el reparto el territorio occidental comprendido entre los rios Tajo y Eljas, que mas ganaderos que agricultores, prefirieron dedicarse mejor al cuidado del ganado cabrío, para cuyo desarrollo eran propicias estas abruptas tierras, dejando la agricultura para los hispanovisigodos. El contrato de arrendamiento se ajusta generalmente poniendo el colono las semillas y las bestias para la labor, que estaba obligado a entregar el dueño una cuarta parte de la producción y algunas cabezas de ganado ovino y cabrío. Los árabes introducen el pastoreo de ovejas, cultivos de algodón, azafrán y los agrios (naranjos de Acebo). También adquirió gran importancia en toda Sierra de Gata el cultivo del olivo. Norias, acequias y aceñas riegan los nuevos cultivos hortícolas. En pocos años se produce el esplendor económico de la zona, almazaras para fabricación de aceite, ferias y mercados estimulan el comercio.

En el siglo X , a partir del califato de Abderramán III, la pacificación y la Islamización de la región van de la mano. En esta época el eclipse de Mérida (acentuado desde la demolición de sus fortificaciones en la segunda mitad del siglo IX) favorece el desarrollo y engrandecimiento de Badajoz, que termina convirtiéndose en la ciudad más importante de Extremadura.

Será por ello por lo que los reyes taifas de la dinastía aftasí, que se independizan del califato a principios del siglo XI sitúen la capital de su reino en Badajoz. El explendor cultural del reino aftasí no implicó la estabilidad política del mismo. Muy al contrario, sus continuas disputas con los reyes taifas de Sevilla primero y la presión de los reyes castellanos después significaron una permanente amenaza para su integridad territorial, que fué mermando continuamente. Serán, sin embargo los Almorávides los que acaben con el reino Aftasí y hagan retroceder a los Cristianos hasta el piedemonte norextremeño. Tras ellos los Almohades detendrán por segunda vez el avance castellanoleonés.

Durante los siglos IX,X y XI tuvo lugar la construcción de diversos castillos: los cristianos realizan distintas incursiones para saquear la comarca de Sierra de Gata. Ramiro II (siglo X) toma temporalmente y fortifica la población de Coria. Otras fortificaciones se construyen como defensa: Torre de la Almenara (siglo IX) en Gata, San Juan de Máscoras (actual Santibañez el Alto, siglo XI) , castillo de Trevejo (siglo XI), de esta época son también las ruinas del Fuerte de vigilancia de Milana (Torre de Milanos ), cerca de Villasbuenas de Gata.