Después de varios desencuentros con el rey de Castilla, hacia 1088 el Cid comenzó a actuar como un caudillo independiente, controlando todo el Levante. Saqueó la taifa de Denia, derrotó a las tropas aliadas del conde de Barcelona y del emir de Lérida en Tévar, y en junio de 1094 tomó Madinat Balansiya, derrotando en Quart al ejército almorávide que había acudido en su auxilio. Desde aquí trato de sentar las bases de un inestable estado sostenido por las armas, buscando el apoyo del obispo de Toledo para legitimar su particular cruzada.

En otoño de 1093 el Cid puso cerco a Madinat Balansiya, destruyendo los arrabales para forzar la rendición de la ciudad, que capituló nueve meses después, tras un asedio angustioso. Los sitiadores no permitieron siquiera el sepelio de los muertos en los cementerios extramuros, como solía ser habitual, lo que obligó a abrir fosas en las calles y plazas para enterrar a los que fallecían. Los atroces episodios que se vivieron tras los muros de la medina quedaron registrados en el poema “Elegía de Valencia” de Abu-l-Walid al-Waqqasi. 

Los reinos de taifas surgidos en al-Andalus tras la descomposición del califato crearon cortes palaciegas, a imitación de Córdoba, que atrajeron literatos, juristas, funcionarios y sobre todo artesanos. Las primeras décadas fueron boyantes, y permitieron, por ejemplo, la erección de la espléndida muralla de Balansiya, levantada por el emir Abd al-Aziz (1021-1061). Sin embargo, la opulencia de los pequeños estados atrajo pronto la codicia de los reinos cristianos. Fernando I, rey de Castilla y León, atacó la ciudad en 1065, fingió retirarse y provocó una masacre entre los imprudentes defensores que salieron en su persecución. Fue la primera de otras muchas acometidas que siguieron en las décadas siguientes. 

A partir de 1065 la taifa de Valencia tuvo dificultades para mantener su autonomía frente a las más poderosas de Zaragoza y, especialmente, Toledo. Además seguía pagando fuertes tributos a los estados cristianos, que saldaba acuñando moneda de baja ley. En 1085, el rey de Toledo, al-Qadir, entregó el trono a Alfonso VI de Castilla a cambio de que éste le garantizara la taifa de Valencia. A pesar de la abierta hostilidad de sus habitantes, al-Qadir entró en Madinat Balansiya un año después, sostenido por las tropas castellanas mandadas por Alvar Fáñez, a las que mantenía a costa de imponer nuevos tributos a la población. Ese mismo año, los almorávides entraban en la Península, ocupando una a una las diferentes taifas y frenando el avance cristiano. 

Enardecidos por las victorias de los almorávides, y al conocer que habían alcanzado ya el Júcar, en el verano de 1092 los valencianos se sublevaron contra al-Qadir, le mataron y entregaron el poder al cadí Ibn Yahhaf, miembro de un ilustre linaje local. El Cid se presentó casi de inmediato ante Madinat Balansiya, exigiéndole sumisión a aquél. Las discrepancias entre las facciones de la oligarquía, partidarios unos de resistir hasta la llegada de los almorávides y otros del acuerdo con los castellanos, echaron por tierra el inestable status quo. El Cid conquistó la ciudad en junio de 1094 y de inmediato arrestó y quemó vivo a Ibn Yahhaf en represalia.