information:classification
Moorish service

The exile was not the end of El Cid, either physically or as an important figure. After being rejected by Ramon Berenguer II, El Cid journeyed to the Taifa of Zaragoza, where he received a warmer welcome. In 1081, El Cid went on to offer his services to the king of Zaragoza, Yusuf al-Mu'taman ibn Hud, and served both him and his successor, al-Musta'in II. He was given the title El Cid (The Master) and served as a leading figure in a diverse Moorish force consisting of Muwallads, Berbers, Arabs, and Malians within the respective Taifa.

According to Moorish accounts:

Andalusi Knights found El Cid their foe ill, thirsty and exiled from the court of Alfonso, he was presented before the elderly Yusuf al-Mu'taman ibn Hud and accepted command of the forces of the Taifa of Zaragoza as their Master.

In his History of Medieval Spain (Cornell University Press, 1975), Joseph F. O'Callaghan writes:

That kingdom was divided between al-Mutamin (1081–1085) who ruled Zaragoza proper, and his brother al-Mundhir, who ruled Lérida and Tortosa. El Cid entered al-Mutamin's service and successfully defended Zaragoza against the assaults of al-Mundhir, Sancho I of Aragón, and Ramon Berenguer II, whom he held captive briefly in 1082.

In 1082, the army of the Taifa of Zaragoza under El Cid defeated the Taifa of Lleida at the Battle of Almenar. In 1084, he defeated the Aragonese at the Battle of Morella near Tortosa, but in autumn the Castilians started a loose siege of Toledo and later the next year the Christians captured Salamanca, a stronghold of the Taifa of Toledo.

In 1086, the Almoravid invasion of the Iberian Peninsula, through and around Gibraltar, began. The Almoravids, a Berber dynasty from North Africa, led by Yusuf ibn Tashfin, were asked to help defend the divided Moors from Alfonso. The Almoravid army, joined by that of several Taifas, including Badajoz, Málaga, Granada, Tortosa and Seville, defeated a combined army of León, Aragón, and Castile at the Battle of Sagrajas.

In 1087, Raymond of Burgundy and his Christian allies attempted to weaken the Taifa of Zaragoza's northernmost stronghold by initiating the Siege of Tudela and Alfonso captured Aledo, Murcia, blocking the route between the Taifas in the eastern and western Iberian Peninsula.