Abd al-Rahman and a small part of his family fled Damascus, where the center of Umayyad power had been; people moving with him included his brother Yahya, his four-year-old son Sulayman, and some of his sisters, as well as his Greek mawla (freedman or client), Bedr.

The 17th-century historian Ahmed Mohammed al-Maqqari poignantly described Abd al-Rahman's reaction as he implored Yahya to keep going: "O brother!

Al-Maqqari quotes earlier historians reporting that Abd al-Rahman was so overcome with fear that from the far shore he ran until exhaustion overcame him.

At the time, Abd al-Rahman ibn Habib al-Fihri was the semi-autonomous governor of Ifriqiya (roughly, modern Tunisia) and a former Umayyad vassal.

The ambitious Ibn Habib, a member of the illustrious Fihrid family, had long sought to carve out Ifriqiya as a private dominion for himself.

He feared the presence of prominent Umayyad exiles in Ifriqiya, a family more illustrious than his own, might become a focal point for intrigue among local nobles against his own usurped powers.

At the time, Abd al-Rahman and Bedr were keeping a low profile, staying in Kabylie, at the camp of a Nafza Berber chieftain friendly to their plight.

When Ibn Habib's soldiers entered the camp, the Berber chieftain's wife Tekfah hid Abd al-Rahman under her personal belongings to help him go unnoticed.

[11] At that moment, the nominal ruler of al-Andalus, emir Yusuf ibn Abd al-Rahman al-Fihri—another member of the Fihrid family and a favorite of the old Arab settlers (baladiyun), mostly of south Arabian or "Yemeni" tribal stock—was locked in a contest with his vizier (and son-in-law) al-Sumayl ibn Hatim al-Kilabi, the head of the "Syrians"—the shamiyun, drawn from the junds or military regiments of Syria, mostly of north Arabian Qaysid tribes—who had arrived in 742.

[12] Among the Syrian junds were contingents of old Umayyad clients, numbering perhaps 500,[12] and Abd al-Rahman believed he might tug on old loyalties and get them to receive him.

The emir Yusuf al-Fihri had proven himself unable to keep the powerful al-Sumayl in check and several Yemeni chieftains felt their future prospects were poor, whether in a Fihrid or Syrian-dominated Spain, so that they had a better chance of advancement if they hitched themselves to the glitter of the Umayyad name.

When some local Berber tribesmen learned of Abd al-Rahman's intent to set sail for al-Andalus, they quickly rode to catch up with him on the coast.

One of the Berbers held on to Abd al-Rahman's vessel as it made for al-Andalus, and allegedly had his hand cut off by one of the boat's crew.

Upon landing in Torrox, al-Andalus, Abd al-Rahman was greeted by clients Abu Uthman and Ibn Khalid and an escort of 300 cavalry.

Waves of people made their way to Málaga to pay respect to the prince they thought was dead, including many of the aforementioned Syrians.

An attempt at negotiations soon followed in which it is likely that Abd al-Rahman was offered the hand of al-Fihri's daughter in marriage and great wealth.

After a long and difficult fight "Abd ar-Rahman obtained a most complete victory, and the field was strewn with the bodies of the enemy.".

Abd al-Rahman's appointed governor in Sevilla took up the chase, and after a series of small fights, managed to defeat al-Fihri's army.

[citation needed] However, in order to take over southern Iberia, al-Fihri's general, al-Sumayl, had to be dealt with, and he was garroted in Córdoba's jail.

In the meantime, a call went out through the Muslim world that al-Andalus was a safe haven for friends of the house of Umayya, if not for Abd al-Rahman's scattered family that managed to evade the Abbasids.

Far away in Baghdad, the current Abbasid caliph, al-Mansur, had long been planning to depose the Umayyad who dared to call himself emir of al-Andalus.

In the year 777–778, several notable men including Sulayman ibn Yokdan al-Arabi al-Kelbi,[20] the self-appointed governor of Zaragoza, met with delegates of the leader of the Franks, Charlemagne.

After capturing Sulayman, Charlemagne's force eventually headed back to France via a narrow pass in the Pyrenees, where his rearguard was wiped out by Basque and Gascon rebels (this disaster inspired the epic Chanson de Roland).

In order to successfully rule in such a situation, Abd al-Rahman needed to create a reliable civil service and organize a standing army.

Abd al-Rahman continued to allow Jews and Christians and other monotheistic religions to retain and practice their faiths, in exchange for the jizya.

There was a great deal of freedom of interaction among the groups: for example, Sarah, the granddaughter of the Visigoth king Wittiza, married a Muslim man and bore two sons who were later counted among the ranks of the highest Arab nobility.

Abd al-Rahman I was able to forge a new Umayyad dynasty by standing successfully against Charlemagne, the Abbasids, the Berbers, and other Muslim Spaniards.

They asked who it was, and al-Mansur replied:[41] The falcon of Quraysh is Abd al-Rahman, who escaped by his cunning the spearheads of the lances and the blades of the swords, who after wandering solitary through the deserts of Asia and Africa, had the boldness to seek his fortune without an army, in lands unknown to him beyond the sea.

Having naught to rely upon save his own wits and perseverance, he nonetheless humiliated his proud foes, exterminated rebels, organized cities, mobilized armies, secured his frontiers against the Christians, founded a great empire and reunited under his scepter a realm that seemed already parcelled out among others.

Mu'awiya rose to his stature through the support of Umar and Uthman, whose backing allowed him to overcome difficulties; Abd al-Malik, because of previous appointment; and the Commander of the Faithful [i.e. al-Mansur himself] through the struggle of his kin and the solidarity of his partisans.