Després de diverses desavinences amb el rei de Castella, cap a 1088 el Cid va començar a actuar com un cabdill independent, controlant tot el Llevant. Va saquejar la taifa de Denia, derrotà a les tropes aliades del comte de Barcelona i de l'emir de Lleida a Tévar, i al juny de 1094 va prendre Madinat Balansiya, derrotant a Quart a l'exèrcit almoràvit que havia acudit en el seu auxili. Des d'ací va tractar de posar les bases d'un inestable estat sostingut per les armes, cercant el suport del bisbe de Toledo per a legitimar la seua particular croada.

A la tardor de 1093 el Cid va posar setge a Madinat Balansiya, destruint els ravals per a forçar la rendició de la ciutat, que va capitular després de nou mesos angoixants. Els assetjadors no van permetre ni tan sols el sepeli dels morts en els cementeris extramurs, com solia ser habitual, la qual cosa va obligar a obrir fosses en els carrers i places per a soterrar als que morien. Els esgarrifosos episodis que es van viure darrere els murs de la medina van quedar registrats en el poema “Elegia de València” d'Abu-l-Walid al-Waqqasi. 

Els regnes de taifas sorgits en al-Andalus després de la descomposició del califat van crear corts palatines, a imitació de Còrdova, que van atraure literats, juristes, funcionaris i sobretot artesans. Les primeres dècades van ser pròsperes, i van permetre, per exemple, l'erecció de l'esplèndida muralla de Balansiya, alçada per l'emir Abd al-Aziz (1021-1061). No obstant açò, l'opulència dels menuts estats va atraure prompte la cobdícia dels regnes cristians. Fernando I, rei de Castella i Lleó, va atacar la ciutat en 1065; fingint retirar-se, va provocar una massacre entre els imprudents defensors que van eixir en la seua persecució. Va ser la primera de moltes altres escomeses que seguiren en les dècades següents.

A partir de 1065 la taifa de València va tindre dificultats per a mantenir la seua autonomia enfront de les més poderoses de Saragossa i, especialment, Toledo. A més seguia pagant forts tributs als estats cristians, que saldava encunyant moneda de baixa llei. En 1085, el rei de Toledo, al-Qadir, va lliurar el tron a Alfonso VI de Castella a canvi que éste li garantira la taifa de València. Malgrat l'oberta hostilitat dels seus habitants, al-Qadir va entrar a Madinat Balansiya un any després, sostingut per les tropes castellanes manades per Alvar Fáñez, a les quals mantenia a costa d'imposar nous tributs a la població. Aqueix mateix any, els almoràvits entraven a la Península, ocupant una a una les diferents taifes i frenant l'avanç cristià. 

Enfervorits per les victòries dels almoràvits, i en conèixer que havien arribat ja al Xúquer, en l'estiu de 1092 els valencians es van alçar contra al-Qadir, el mataren i li van lliurar el poder al cadí Ibn Yahhaf, membre d'un il•lustre llinatge local. El Cid es va presentar quasi de seguida davant Madinat Balansiya, exigint-li submissió a aquell. Les discrepàncies entre les faccions de l'oligarquia, partidaris uns de resistir fins a l'arribada dels almoràvits i uns altres de l'acord amb els castellans, van tirar per terra l'inestable status quo. El Cid va conquistar la ciutat al juny de 1094 i immediatament va arrestar i va cremar viu a Ibn Yahhaf en represàlia.