En el año 1241 accede al trono de Murcia otro ilustre miembro de la familia hudí, Ibn Hûd Bahâ al-Daula, que supo mantenerse en el poder durante dos décadas y afrontar la delicada situación política de su reino. La presión militar de castellanos y aragoneses sobre la frontera era tan evidente como el desmembramiento político a consecuencia de la débil autoridad del rey musulmán. En ese contexto político la única salida de los reyezuelos musulmanes era sellar un pacto de vasallaje con Castilla que le permitiera ganar tiempo con el fin de reorganizarse.
El tratado de Alcaraz
Los primeros contactos diplomáticos tuvieron como escenario la ciudad de Toledo, donde la embajada de los musulmanes murcianos garantizó la entrega de la ciudad de Murcia y de todos los castillos situados entre Alicante, Lorca y Chinchilla, entre los que cabe incluir el de Aledo. La firma del Tratado de Alcaraz en 1243 es quizás el pacto político de mayor relevancia en la historia de la Región, pues simboliza el final de la hegemonía musulmana sobre el sureste peninsular y el inicio de una tímida pero inexorable implantación de los cristianos. El arraez (jefe militar) de Aledo, como máximo representante de la comunidad musulmana, también participó en ese mítico pacto.
En abril de 1243 el infante don Alfonso se trasladó con sus huestes (tropas) a Alcaraz para entrevistarse con un hijo del rey Ibn Hud a quien acompañaban los máximos representantes de otros núcleos independientes del reino murciano entre los que se mencionan Aledo, Alhama, Alicante, Cieza, Orihuela y otros lugares. La presencia de un representante de Aledo entre los firmantes del pacto, evidencia que esta población también debió participar de las ventajosas condiciones conseguidas con el pacto frente a otros núcleos que fueron tomados a la fuerza.
De la misma manera que ocurrió con el resto de los núcleos sometidos a vasallaje, a los cristianos se les debió entregar la alcazaba de Aledo y dos tercios de las rentas o impuestos recaudados en su término. En contraprestación, las autoridades castellanas estaban obligadas a respetar la religión, leyes, bienes y autoridad de los musulmanes.
Durante los primeros quince años de vigencia de los acuerdos de Alcaraz, firmados entre castellanos y musulmanes, la vida cotidiana de la población que habitaba en Aledo no debió sufrir variaciones dignas de consideración. Como en el resto del reino, las familias mudéjares con mayor poder adquisitivo abandonarían su tierra para emigrar a la vecina Granada o al norte de África. La mayor parte de la población sin embargo, se mantendría en Aledo, ajena a los profundos cambios que pronto se iban a producir.
Alfonso X y el privilegio rodado
El año 1257 fue fundamental para la transformación de la antigua taifa o reino musulmán de Murcia en un reino cristiano, plenamente integrado en la Corona de Castilla. Ese año Alfonso X permaneció seis meses en el reino de Murcia, visitando las ciudades de Orihuela, Alicante, Cartagena, Lorca, Elche y Murcia. La política alfonsí encaminada a aminorar la influencia de los súbditos musulmanes en su territorio se hace patente en una serie de disposiciones que procuran castellanizar el territorio desde el punto de vista demográfico, administrativo y político.
Todo ello toma cuerpo en un Privilegio Real expedido desde Cartagena el 14 de abril de 1257; en ese documento, quizás el más relevante en la historia de Aledo, el rey sabio hace cesión de todas sus prerrogativas jurisdiccionales a los representantes de la orden santiaguista cuando afirma "que ellos que tengan a los moros de Aledo e de Totana todos los pleitos".