Primer destierro: al servicio de la taifa de Zaragoza
Sin descartar del todo la posible influencia de cortesanos opuestos a Rodrigo Díaz en la decisión, la incursión del castellano contra el territorio de al-Qadir, el régulo títere de Toledo protegido de Alfonso, le causó el destierro y la ruptura de la relación de vasallaje.
Junto con sus vasallos o «mesnada» se estableció desde 1081 hasta 1086 como guerrero bajo las órdenes del rey de Zaragoza al-Muqtadir, quien, gravemente enfermo, fue sucedido en 1081 por al-Mutamán. Este encomendó al Cid en 1082 una campaña contra su hermano el gobernador de Lérida Mundir, el cual, aliado con el conde Berenguer Ramón II de Barcelona y el rey de Aragón Sancho Ramírez, no había acatado el poder de Zaragoza a la muerte del padre de ambos, desatándose una guerra fratricida entre los dos reyes hudíes del Valle del Ebro.
La hueste del Cid reforzó las plazas fuertes de Monzón y Tamarite y derrotó a la coalición, formada por Mundir y Berenguer Ramón II, ya con el apoyo del grueso del ejército taifal de Zaragoza, en la batalla de Almenar, donde fue hecho prisionero el conde Ramón Berenguer II.
En 1084 el Cid desempeñaba una misión en el sureste de la taifa zaragozana, atacando Morella, posiblemente con la intención de que Zaragoza obtuviera una salida al mar. Al-Mundir, señor de Lérida, Tortosa y Denia, vio en peligro sus tierras y recurrió esta vez a Sancho Ramírez de Aragón, que combatió contra Rodrigo Díaz el 14 de agosto de 1084 en la batalla de Morella, también llamada de Olocau —si bien en 2005 Boix Jovaní postuló que se desarrolló algo más al norte de Olocau del Rey, en Pobleta d’Alcolea—. De nuevo el castellano se alzó con la victoria, capturando a los principales caballeros del ejército aragonés (entre los que se encontraban el obispo de Roda Ramón Dalmacio o el tenente del condado de Navarra Sancho Sánchez) a quienes seguramente liberaría tras cobrar su rescate. En alguno de estos dos recibimientos apoteósicos en Zaragoza podría haberse recibido al Cid al grito de «sīdī» (‘mi señor’ en árabe andalusí, a su vez proveniente del árabe clásico sayyid), el apelativo romanceado de «mio Çid».
Reconciliación con Alfonso VI
El 25 de mayo de 1085 Alfonso VI conquista la taifa de Toledo y en 1086 inicia el asedio a Zaragoza, ya con al-Musta’in II en el trono de esta taifa, quien también tuvo a Rodrigo a su servicio. Pero a comienzos de agosto de ese año un ejército almorávide avanzó hacia el interior del reino de León, donde Alfonso se vio obligado a interceptarlo, con resultado de derrota cristiana en la batalla de Sagrajas el 23 de octubre. Es posible que durante el cerco a Zaragoza Alfonso se reconciliara con el Cid, pero en todo caso el magnate castellano no estuvo presente en Sagrajas. La llegada de los almorávides, que observaban más estrictamente el cumplimiento de la ley islámica, hacía difícil para el rey taifa de Zaragoza mantener a un jefe del ejército y mesnada cristianos, lo que pudo causar que prescindiera de los servicios del Campeador. Por otro lado, Alfonso VI pudo condonar la pena a Rodrigo ante la necesidad que tenía de valiosos caudillos con que enfrentarse al nuevo poder de origen norteafricano.
Cuando llegó, Valencia estaba siendo sitiada por Berenguer Ramón II, ahora aliado con al-Musta’in II de Zaragoza, a quien el Campeador había negado entregar la capital levantina en la campaña anterior. Rodrigo, ante la fortaleza de esta alianza, procuró un acuerdo con al-Mundir de Lérida y pactó con el conde de Barcelona el levantamiento del asedio, que este hizo efectivo. Posteriormente, El Cid comenzó a cobrar para sí mismo las parias que anteriormente Valencia pagaba a Barcelona o al rey Alfonso VI y estableció con ello un protectorado sobre toda la zona, incluida la taifa de Albarracín y Murviedro.
