Las tropas de la taifa valenciana sufrieron una contundente derrota en 1065 ante las fuerzas de Fernando I de Castilla y León, y la pérdida de su capacidad militar hizo que Balansiya quedase sometida a Al-Mamun, rey de la taifa de Toledo, hasta su muerte en 1075. Tras la conquista de Toledo por los castellanos en 1085, el destronado emir Al-Qadir, obtuvo el control de Valencia como nueva taifa que gobernar. Al poco tiempo de asumir su cargo Al-Qadir ya era extremadamente impopular entre la población de la ciudad, debido a su dependencia de mercenarios cristianos para mantenerse en el poder, los motines populares y protestas de la población fueron constantes, al igual que los ataques de los emires vecinos. En uno de estos ataques, por parte del emir zaragozano, participó el Cid, el cual fue sobornado por Al-Qadir para que entrara a su servicio, aunque sería el castellano quien ejerciera el verdadero poder por la debilidad del reyezuelo.
Mientras tanto, en el norte de África surgía el poder de los almorávides, el cual sería una amenaza tanto para los cristianos como para los andalusíes. Los almorávides eran tribus nómadas originarias del desierto norteafricano que abrazaron una interpretación rigorista del islam predicada por un ermitaño llamado Ibn Yasin. A mediados del siglo XI establecieron sus primeras bases en la costa de Senegal, desde allí comenzaron a conquistar territorios y acabaron dominando gran parte del noroeste de África, estableciendo su capital en la recién fundada Marrakech.Tras la descomposición del califato de Córdoba, la España musulmana se dividió en multitud de pequeños reinos, las taifas, incapaces de defenderse de los reinos cristianos por su debilidad militar. Tras la conquista de Toledo por Alfonso VI, el reyezuelo de Sevilla reclamó ayuda a los almorávides, y su emir Yusuf Ibn Tasufin cruzó el estrecho con un ejército, derrotando a las fuerzas de Alfonso VI en Sagrajas en 1086.
Tal petición de ayuda se hizo con grandes reticencias por parte de algunos de los emires andalusíes, temerosos del fanatismo almorávide y de que aprovechasen la oportunidad para someter a los debilitados musulmanes de la Península. Tras vencer a los cristianos, los norteafricanos volvieron a sus tierras.Sin embargo, los castellanos se recuperaron, y reanudaron sus ataques a los andalusíes, y éstos volvieron a pedir ayuda a los africanos en 1090. Tasufin acudió aparentemente en su auxilio, pero su verdadero objetivo era la conquista de las taifas y frenar el avance cristiano, lo que consiguió en una sucesión de rápidas campañas.
Los almorávides contaron con el apoyo del clero y del pueblo, entre los que existía un profundo malestar por ser obligados a pagar impuestos para obtener los tributos exigidos por los monarcas cristianos o para pagar los salarios de los mercenarios en los que se apoyaban los emires de muchas taifas.
Los almorávides consolidaron su poder en la península derrotando nuevamente a los castellanos en Consuegra (1097) y Uclés (1108), siendo el Cid el único capaz de combatirlos con éxito. A pesar de ello, el dominio almorávide en la península fue efímero, su fanatismo acabó despertando el malestar de los andalusíes que con tanto entusiasmo acogieron su llegada, este descontento fue el origen de muchas revueltas, a lo que se une la rápida recuperación de los cristianos, Alfonso VII de Castilla y Alfonso I de Aragón les derrotaron en varias batallas y pudieron recuperar las tierras perdidas por el avance inicial de los almorávides y conquistar nuevas regiones que pasaron a manos cristianas definitivamente.Las derrotas en la península causaron la división de las tribus que formaron el movimiento almorávide, dando inicio a luchas internas, y en su momento de mayor debilidad, apareció otro movimiento similar, los almohades, formado por las tribus de las montañas del Atlas en Marruecos, que comenzaron a hacerse con el control del norte de África, hasta que derrotaron definitivamente a los almorávides en la década de 1140 y los sustituyen como el poder dominante en África.