Berber and that he first took refuge with the Nafsa Berbers, his mother's people. As the governor Ibn Habib was seeking him, he then fled to the more powerful Zenata Berber confederacy, who were enemies of Ibn Habib. Since the Zenata had been part of the initial invasion force of al-Andalus, and were still present in the Iberian peninsula, this gave Abd ar-Rahman a base of support in al-Andalus, although he seems to have drawn most of his support from portions of Balj's army that were still loyal to the Umayyads. Abd ar-Rahman crossed to Spain in 756 and declared himself the legitimate Umayyad ruler of al-Andalus. The governor, Yusuf, refused to submit. After losing the initial battle near Cordoba, Yusuf fled to Mérida, where he raised a large Berber army, with which he marched on Seville, but was defeated by forces loyal to Abd ar-Rahman. Yusuf fled to Toledo, and was killed either on the way or after reaching that place. Yusuf's cousin Hisham ibn Urwa continued to resist Abd ar-Rahman from Toledo until 764, and the sons of Yusuf revolted again in 785. These family members of Yusuf, members of the Fihri tribe, were effective in obtaining support from Berbers in their revolts against the Umayyad regime. As emir of al-Andalus, Abd ar-Rahman I faced persistent opposition from Berber groups, including the Zenata. Berbers provided much of Yusuf's support in fighting Abd ar-Rahman. In 774, Zenata Berbers were involved in a Yemeni revolt in the area of Seville. Andalusi Berber Salih ibn Tarif declared himself a prophet and ruled the Bargawata Berber confederation in Morocco in the 770s. In 768, a Miknasa Berber named Shaqya ibn Abd al-Walid declared himself a Fatimid imam, claiming descent from Fatimah and Ali. He is mainly known from the work of the Arab historian Ibn al-Athir, who wrote that Shaqya's revolt originated in the area of modern Cuenca, an area of Spain that is mountainous and difficult to traverse. Shaqya first killed the Umayyad governor of the fortress of (near Roman Ercavica), and subsequently ravaged the district surrounding Coria. Abd ar-Rahman sent out armies to fight him in 769, 770, and 771; but Shaqya avoided them by moving into the mountains. In 772, Shaqya defeated an Umayyad force by a ruse and killed the governor of the fortress of Medellin. He was besieged by Umayyads in 774, but the revolt near Seville