Durante los primeros siglos de dominio musulmán lentamente se forja en Al-Andalus (España musulmana) una nueva sociedad muy compleja y multicultural. A la población hispanovisigoda se suman nuevos colonos musulmanes llegados de Oriente, pero en general la población permanece escasamente islamizada y arabizada.
El peso específico del Estado Omeya, con capital en Córdoba, era también escaso en el sureste peninsular, de ahí la iniciativa por parte del emir cordobés Abd al-Rahman II de fundar Murcia en el centro del territorio, como nueva capital administrativa que fuera capaz de vertebrar el territorio. La presencia de Aledo entre Lorca y Murcia, las dos ciudades más importantes de Tudmîr, la convertiría en un enclave de vital importancia para dominar la frontera oriental y toda la provincia de Tudmîr.
Entre los asentamientos que configuran la Cora de Tudmîr o provincia del sureste peninsular, el de Aledo muy pronto se convertiría en uno de núcleos fortificados más antiguos y relevantes. El término árabe hîsn (plural hûsun), evidencia que los aledanos musulmanes fueron capaces en un intervalo de tiempo relativamente corto de constituir un núcleo que se encontraba a caballo entre lo urbano y lo rural. Era una población de inferior categoría a una ciudad (o madîna) pero de mayor importancia administrativa y económica que una simple alquería o cortijo de carácter rural.
La revuelta muladí
Tras varios siglos de silencio, Aledo entra en la Historia de España por la puerta grande, en el contexto de un conflicto bélico que salpica todo el territorio de Al-Andalus. En el año 883, el descontento de la población indígena, cristiana y muladí (descendiente de cristiano recientemente convertido al Islam) fue aprovechado por el muladí Omar b. Hafsun (descendiente de una familia goda) para encabezar una revuelta que puso en jaque al poder del Estado, llegando a controlar una extensa área de Andalucía. Este mítico personaje finalmente se convertiría al cristianismo en el año 899 y llegaría a instaurar un obispo cristiano en el enclave malagueño de Bobastro.
Esa rebelión también fue secundada en el territorio de Tudmîr, donde los sublevados fueron dirigidos por otro muladí, Daysam b. Isaac, personaje que disfrutaba de gran prestigio entre sus conciudadanos. La primera mención de Aledo se debe a un famoso autor árabe llamado Ibn Hayyân (Muqtabis 116-117), quien narra con detalle las revueltas acontecidas en la última década del siglo IX. En este episodio, Aledo se confirma como uno de los lugares donde se habían refugiado los muladíes. Ante esa situación, el emir cordobés Abd Allâh (888-912) decidió realizar una campaña militar en el sureste peninsular para acabar con la revuelta, pacificar el territorio y reestablecer el control el Estado.
Tras someter el resto de Andalucía, la campaña de Tudmîr se llevaría a cabo en el año 896. El principal objetivo era recobrar el control de Murcia y Lorca, las principales ciudades de la cora (provincia administrativa). Según el relato de Ibn Hayyân, el poderoso ejército de Abd Allâh tras tomar Ricote, se dirigió a la capital donde no encontró resistencia.
En la ribera del río Segura permaneció acampado durante diez días, en el transcurso de los cuales, cobró los impuestos y se abasteció de víveres. Desde Murcia marchó con sus tropas hacia Lorca, pero durante el trayecto perecieron treinta hombre y muchas acémilas por falta de de agua, razón por la cual se dirigió al paraje, que algunos autores sitúan entre Alhama de Murcia y Aledo, denominado Ayn Saytûn (la Fuente del Diablo). Desde este lugar marchó a Aledo, donde acampó con sus ejércitos y desde Aledo envió emisarios a Daysam que se encontraba en el castillo de Lorca pidiéndole que se rindiera.
El primer asedio por parte de las tropas enviadas por emir Abd Allâh sería uno más de los muchos sufridos en la historia de Aledo. El hecho de que fuera asediada por un potente ejército es indicativo también de que en ese momento ya disponía de unas defensas de consideración. Por sus magníficas condiciones como enclave estratégico, el castillo aledano siempre estuvo en el "ojo del huracán" de los principales episodios bélicos de la España medieval (ver vídeo).