En el año 1079 es enviado por Alfonso VI a cobrar las parias del rey de Sevilla Motámid. Malos días fueron pues el conde de Nájera, García Ordoñez andaba cobrando parias en Granada y no se le courrió mejor idea que atacar al defendido del Cid. Éste tomó las armas y se cobró varios prisioneros entre los cristianos, entre ellos el propio Conde.

Herido en su orgullo el susodicho Conde empieza a manipular en contra del Cid en la Corte real y dos años después tras otro suceso semejante es desterrado de Castilla.

En 1081 el Cid es desterrado (para más información vaya aquí) y empieza su vida como soldado a sueldo junto con su pequeño pero eficaz ejército. Su primer destino fue Zaragoza donde el rey taifa al-Muqtadir le pidió ayuda contra Castilla, Navarra y Aragón y contra los condes de Urgel y de Barcelona, él se la concedió pues ya no debía vasallaje a nadie. En la batalla de Almenara (1082) el Cid venció a numeroras tropas navarro-aragonesas y las del conde de Barcelona, hubo miles deprisioneros pero dejó libre a todos excepto a algunos favoritos, como el mismo conde barcelonés que tuvo que pagar una fuerte suma por su vida. Esto le hizo imprescindoble en el reino taifa zaragozano.