La derrota en 1065 ante las fuerzas de Fernando I dejó en posición de debilidad a la taifa valenciana ante las agresiones de otras taifas y de los reyes cristianos, en especial de Castilla, cuyos monarcas sometieron a Balansiya al pago de fuertes tributos. En 1085, Alfonso VI de Castilla tomaba Toledo, y el emir Al-Qadir recibía como compensación el control de la taifa valenciana. Su dependencia de mercenarios cristianos le granjeó el odio de la población, cuyos impuestos servían para pagar a las tropas que mantenían al emir en el trono. Posteriormente, cuando sus enemigos se univeron para derrotarle, Al-Qadir consiguió que el Cid, comandante de parte de las tropas enemigas, se pusiera de su parte, aunque el verdadero objetivo del castellano era ejercer el poder de manera indirecta, controlando al emir. Para ello el Cid tuvo que hacer frente a varios desafíos para mantener la situación de acuerdo a sus intereses. Alfonso VI deseaba recuperar el control de la taifa, y procedió a asediar la capital, pero la respuesta del Cid fue reunir a sus tropas y dirigirse a Castilla, donde saqueó La Rioja, obligando al rey castellano a retirarse para defender sus dominios. Sin embargo, este movimiento dejó indefenso a Al-Qadir, y sus enemigos en la ciudad lo aprovecharon. Muchos de ellos eran partidarios de los almorávides y buscaban obtener su apoyo en el enfrentamiento con los cristianos. Se produjo una revuelta liderada por Ibn Yahhaf, un cadí perteneciente a una de las familias más influyentes de la ciudad, y el emir fue ejecutado.
Acto seguido, los rebeldes enviaron una petición de ayuda a los almorávides, que ya dominaban Murcia, para someterse a ellos e integrarse en su imperio. El Cid volvió en ese momento, y asedió Valencia, los alzados decidieron resistir en espera de las tropas almorávides que estaban en camino, pero cuando alcanzaron Almussafes estalló una tormenta que les impidió continuar su avance, y las inundaciones resultantes les obligaron a retirarse sin llegar a combatir. Perdida toda esperanza de recibir ayuda, los sitiados iniciaron las negociaciones para la rendición, y tras un asedio de veinte meses, el Cid pudo entrar en Valencia el 15 de junio de 1094, iniciando una dura represión, en la que muchos personajes importantes fueron ejecutados, entre ellos Ibn Yahhaf. El triunfo del castellano se completó el siguiente mes de septiembre, cuando derrotó a las huestes almorávides que llegaron a la cercanías de la ciudad.
A pesar de la derrota, los almorávides no renunciaron a sus planes de dominar la región, y organizaron una nueva campaña en 1097, pero el Cid obtuvo una nueva victoria sobre los norteafricanos en la batalla de Bairén, cerca de Gandía. En esta victoria tuvieron una gran importancia las tropas aportadas por el rey Pedro I de Aragón, nuevo aliado del Cid, que había aprovechado los años intermedios entre los dos ataques para formar alianzas y organizar sus fuerzas de cara a los previsibles ataques almorávides. Todos los ataques almorávides contra Valencia fueron rechazados por el Cid hasta su muerte en 1099. A partir de ese momento, su viuda doña Jimena gobernó la ciudad como señora con la ayuda del conde Ramón Berenguer III de Barcelona y de los aragoneses, pero los almorávides reanudaron sus ataques con más fuerza y la ciudad ya no pudo ser defendida, las fuerzas castellanas que la defendían tuvieron que retirarse en 1102, tras incendiarla. Después de eso Balansiya volvió a estar bajo control musulmán cuando los almorávides pudieron finalmente hacerse con ella.
: