Mientras el Campeador permanecía en Zaragoza, la situación en Valencia capital se tornaba cada vez más inestable. La facción proalmorávide de la ciudad crecía desde fines de 1091, estimulada por las conquistas recientes, esperando que el nuevo poder norteafricano podría imponer orden en la agitada y corrupta política de la ciudad, liberando a los musulmanes valencianos de un señorío de facto cristiano y de las alcábalas y otras tasas no sancionadas por la ley islámica.El Cid, antes de marchar a Zaragoza, había dejado como administrador y tesorero de confianza al-wazir de Valencia Ibn Al-Farach a cargo de la recaudación de impuestos que el Campeador recibía. Pero al frente de los afectos a la causa almorávide se situó el cadí de la ciudad Ibn Yahhaf, quien aprovechando la ausencia del Cid durante el año de 1092, prometió al general almorávide Ibn Aisa entregarle Alcira y Valencia. Con la situación muy comprometida en Valencia, en octubre, Rodrigo se decidió a volver, pero ya era tarde.
Ibn Aisa había mandado un destacamento de jinetes almorávides al mando de Ibn Nasr a Alcira, donde tomaron posesión de la plaza. No tardaron en apostarse a las puertas de Valencia. Mientras tanto, el cadí Ibn Yahhaf había detenido a Ibn al-Farach y, con la ayuda de sus partidarios, entre los que figuraban algunos potentados de la ciudad, como el magistrado Ibn Wayib, y los guerreros almorávides venidos desde Alcira, tomaron al asalto la ciudadela valenciana, de donde tuvo que huir el rey Al-Qadir (disfrazado, al parecer, de mujer y mezclado entre su harén) y toda su corte, entre los que se contaban el obispo nombrado por Alfonso VI, la comunidad mozárabe y otros andalusíes cercanos al Cid. Sin embargo, el que había sido rey de Toledo y de Valencia, siempre protegido por los magnates cristianos, solo logró esconderse en una vivienda cercana a ciertos baños públicos. Allí fue localizado por los sublevados con prontitud. Ibn Yahhaf encargó a un descendiente de Abu Bakr ibn al-Hadidi que ejecutara al monarca y vengara así la muerte de su pariente, que Al-Qadir había ordenado cuando reinaba en Toledo. El joven Banu Hadidi decapitó al soberano, su regia cabeza fue paseada por las calles de Valencia clavada en una pica y su cuerpo arrojado a un muladar, donde un vecino piadoso le dio sepultura sin mortaja, cual si se tratara de un indigente. También fue ajusticiado el ex rey de la taifa de Murcia Abu Abderramán Ibn Tahir, quien había socorrido al monarca de Valencia en una ocasión en que fue sitiado por el rey taifa de Denia.
Los fieles al rey supervivientes buscaron refugio en Yubaila/Cebolla, fortaleza gobernada por un mahometano de Albarracín en nombre del señor de la taifa de Alpuente Ibn Qasim. Los exiliados fueron acogidos por el almojarife o tesorero judío del difunto Al-Qadir. Otros se apresuraron a encontrarse con Rodrigo, que ya acudía a Cebolla, para informarle de la revuelta y de la muerte del rey. El Cid había perdido todo su dominio sobre las tierras valencianas a causa del avance almorávide e Ibn Yahhaf, un líder interesado sobre todo en el tesoro que Al-Qadir había escondido en Segorbe y Olocau de Valencia (localidad situada a unos treinta kilómetros de la capital levantina), se había convertido en el nuevo y arrogante príncipe de Valencia.
