In 1086 Yusuf ibn Tashfin was invited by the Muslim taifa princes of Al-Andalus in the Iberian Peninsula to defend their territories from the encroachment of Alfonso VI, King of León and Castile. In that year, Ibn Tashfin crossed the Strait of Gibraltar to Algeciras, and defeated Castile at the Battle of Sagrajas. He was prevented from following up his victory by trouble in Africa, which he chose to settle in person.

He returned to Iberia in 1090, avowedly for the purpose of annexing the taifa principalities of Iberia. He was supported by most of the Iberian people, who were discontented with the heavy taxation imposed upon them by their spendthrift rulers. Their religious teachers, as well as others in the east (most notably, al-Ghazali in Persia and al-Turtushi in Egypt, who was himself an Iberian by birth from Tortosa), detested the taifa rulers for their religious indifference. The clerics issued a fatwa (a non-binding legal opinion) that Yusuf was of sound morals and had the religious right to dethrone the rulers, whom he saw as heterodox in their faith. By 1094, Yusuf had annexed most of the major taifas, with the exception of the one at Zaragoza. The Almoravids were victorious at the Battle of Consuegra, during which the son of El Cid, Diego Rodríguez, perished. Alfonso, with some Leónese, retreated into the castle of Consuegra, which was besieged for eight days until the Almoravids withdrew to the south.