The Rashidun and Umayyad Caliphates conquered the Byzantine Exarchate of North Africa commencing in 647 and concluding in 709, when the Byzantine Empire lost its last remaining strongholds in the Maghreb to Caliph al-Walid I. The North African campaigns form part of Arab-Byzantine wars, as well as part of the century of rapid early Muslim conquests.
Taking nearly 70 years, the conquest of the Maghreb was one of the longest campaigns of the early Muslim conquests. Occurring in fits and starts, the first campaigns began in the 640s soon after the fall of Egypt. In 647, the Byzantine army was defeated at Sufetula in southern Tunisia and a massive tribute was exacted. After a long interim, campaigns restarted in 665, in 670 Uqba ibn Nafi founded Qayrawan, Abu al-Muhajir Dinar began the pivotal rapprochement policy with the Berbers and their large scale recruitment, Numidia was subjugated and in 683 Uqba pushed all the way to the Atlantic, ultimately being defeated upon his return, reversing all Muslim gains. In 694 a new army was sent, taking Carthage and ending the Byzantine presence by 698. Over the next decade Musa ibn Nusayr then conquered modern day Algeria and Morocco, began the mass recruitment and Islamization of the Berbers on a scale unseen elsewhere, and set the stage for the 711 conquest of Iberia.
Background
By 642 AD, under Caliph Umar, Arab Muslim forces had taken control of Mesopotamia (638 AD), Syria (641 AD), Egypt (642 AD), and had invaded Armenia (642 AD), all territories previously split between the warring Byzantine and Sasanian empires, and were concluding their conquest of Sasanian Persia with their defeat of the Persian army at the Battle of Nahāvand. It was at this point that Arab military expeditions into North African regions west of Egypt were first launched, continuing for years and furthering the spread of Islam.
In 644 at Medina, Umar was succeeded by Uthman, during whose twelve-year rule Armenia, Cyprus, and all of modern-day Iran, would be added to the expanding Rashidun Caliphate. With Afghanistan and North Africa being targets of major invasions and Muslim sea raids ranging from Rhodes to the southern coasts of the Iberian Peninsula, the Byzantine navy was defeated in the eastern Mediterranean.
First invasion
Soon after the fall of Alexandria in 642, Amr ibn al-As continued westwards into Cyrenaica and Tripolitania. Perhaps he had an awareness of the Byzantine campaigns on Egypt via North Africa in 608-9 and Heraclius's plan in 633 to move troops from Numidia to bolster Egypt and wished to forestall such an effort.
Heading for Barca he had around 4,000 troops, drawn from the army which conquered Egypt and particularly the reinforcements which accompanied Zubayr ibn al-Awwam, the majority of whom from Yaman (Mahra, Hadramawt, Khawlan, Mu'afir, Lakhm and Sadif) as well as some of the Hejazis (Fihr, Banu Abd al-Uzza and the Ansar) who were under Abdallah ibn al-Zubayr. Barqa fell without opposition, treaties were made with the Luwata Berbers exacting a tribute of 13,000 dinars and Amr sent Uqba ibn Nafi into the Fezzan, successfully taking Zuwayla. Tripoli was more difficult, its garrison being supported by the Christian Berber tribes of Nafusa, but after around a month it also fell in around 643, along with Sirte, Sabratha and Leptis Magna, while Busr ibn Abi Artat took Waddan. Now, with a vast buffer between Byzantine North Africa and Egypt, Amr returned to Fustat, leaving Uqba ibn Nafi as Governor of Barqa.
In late 645 the Byzantines attempted a reconquest of Egypt. Constans II sent Manuel with a large naval force, successfully retaking Alexandria he began to push towards Fustat, until he was stopped in May 646 at Nikiou, a mere 60 km from Fustat. This highlighted the still somewhat insecure Muslim hold on Egypt, prompting campaigns to end all remaining Byzantine military or political threats to the region, such as those to the west.
Meanwhile, in Africa, Exarch Gregory the Patrician rebelled against Constans II following the public disputation between Maximus and Pyrrhus of July 645, declaring himself emperor (perhaps attempting to emulate the successful Heraclian revolt which seized Constantinople via North Africa). However, this rebellion weakened Africa's defences; attempting to wage war independently, without assistance from Constantinople. It also brought to the attention of the Muslims the internal strife and fragilities of the North Africans and their leadership.
The Battle of Sufetula
In 647, governor of Egypt, Abd Allah ibn Sa'd, led a new invasion force, around 20,000 strong, into Africa. Accompanied by many luminaries of the Quraysh: Ma'bad ibn Abbas, Abd Allah ibn Umar, Asim ibn Umar, Ubayd Allah ibn Umar, Abd al-Rahman ibn Zayd ibn al-Khattab, al-Miswar ibn Makhrama, Abd Allah ibn Amr, Abd Allah ibn al-Zubayr, Busr ibn Abi Artat, Marwan ibn al-Hakam, Al-Harith ibn al-Hakam, Abu Dhuʾayb al-Hudhali and others, showing that this was no small raid.
Joined en route by Uqba ibn Nafi and his forces stationed in Barqa, Abd Allah ibn Sa'd first made for Tripoli, which had fallen back into the hands of the Byzantines soon after Amr ibn al-Aas' departure. Then Ghadames, and a place referred to as "Elenptien" by the Chronicle of 754, possibly referring to Leptis Magna, Lamta or Thelepte. After a failed attempt on the southern Tunisian port of Gabes, the Muslims pushed into the interior, towards Gregory's base of operations at Sufetula - a nodal point in southern Tunisia, where the Exarch could dominate the fertile fields of Byzacena while controlling access further west into Numidia or to the north (Zeugitana) via the Kasserine pass. But it was also ideal for the Muslims, as its distance from the coast prevents Byzantine naval interference, while the flat plains of Byzacena means there are no obstacles to cut their lines of communication with Tripolitania.
To avoid a long war of attrition, which would have put the Muslims at a disadvantage due to their limited forces and distance from Egypt, they instead provoked Gregory into a decisive open field battle - probably by raiding the countryside, forcing local elites to pressure Gregory into a confrontation to protect their lands. According to Ibn al Athir it was Abd Allah ibn al-Zubayr who recognised the Muslims' overextension and need for a decisive battle, he then advised Abd Allah ibn Sa'd to leave some elite troops near camp, while the remainder wear down Gregory's soldiers. When the Exarch's forces begin to tire, the Muslims would feign a retreat to the camp, where the fresh troops would suddenly pounce on the Romans And so it happened, with brilliant success. In the summer of 647, the Muslims lured Gregory and his inexperienced troops into pursuing them eastwards (perhaps because Gregory sought to open up communications with the coast to avoid entrapment around Sufetula). Around an hour before sunset, the Muslims unleashed their ambushes, disorienting Gregory's forces, breaking their cohesion and leading to their flight, while Ibn al-Zubayr himself personally slew the Exarch.
After the battle, Abd Allah ibn Sa'd remained in North Africa for the next 14–15 months campaigning in the region and blockading Thysdrus. Eventually the local Romano-African inhabitants, probably under Gennadius, consented to the payment of a humiliating tribute of 2,520,000 dinars or 330,000 solidi if the Muslims left the region. Abd Allah ibn Sa'd agreed and returned to Egypt in 648. The reason for returning so soon, after winning such an overwhelming victory, is probably due to Abd Allah ibn Sa'd recognising that Carthage and the remaining Byzantine coastal cities could only be subdued via Muslim naval power, which was still in its very early infancy. While the 646 Byzantine reconquest of Alexandria further emphasized this need for naval build up, and showed that the east hadn't been fully consolidated yet, so it is improbable that they'd want to establish a settlement or base in the west and risk overextension. Beyond that, the resounding victory at Sufetula meant that there was little threat from Byzantine troops via the Maghreb, so there was much less incentive to pursue further campaigns. Perhaps the huge amount of booty (1,000 dinars for each infantryman, and 3,000 for a horseman) further dissuaded enthusiasm for further campaigns.
For the next 13 years, there was no further engagements between the Muslims and the Byzantines in North Africa. Abd Allah ibn Sa'd instead immediately focused on ending the Byzantine monopoly over the Mediterranean, founding a new dockyard at Roda island building up the Egyptian fleet. Not long after his return from Sufetula, the fleet set forth on its first campaign against Cyprus in 648/649, then raiding Crete, Rhodes and Sicily between 652–654, and returning to Cyprus in 653. In 655 Abd Allah ibn Sa'd personally led the Muslim naval forces and annihilated the Byzantine navy at the Battle of the Masts, rupturing the Byzantine hegemony and opening up the central Mediterranean to the Muslims. But the First Fitna between 656-661 prevented further campaigns - the civil war may have been affected by the significant wealth brought in through the 647 campaign.
Second invasion
After the First Fitna, the Muslims had to restart the conquest of the Maghreb from the beginning. Even in nearby Cyrenaica, their former Luwata Berber allies withdrew their allegiance. In 660 Shurayk ibn Sumayy al-Muradi brought these tribes back under submission. When in 661 these tribes moved west towards Tripoli and again reneged, Uqba ibn Nafi campaigned against them, reaffirming their allegiance. In 662 he took Ghadames. In 663 he and Shurayk took Labda, then Uqba returned to the Fezzan and took Waddan.
After the death of Amr ibn al-As in 664, Caliph Mu'awiya took more direct control over Egypt and the Maghrebi Campaign. To this end, he established a new garrison at Khirbita bordering the Western Desert on the western edge of the delta, this was to serve as an advance base for the campaigns into the Maghreb, appointing Mu'awiya ibn Hudayj as commander of its garrison.
In 665 (or 667) Ibn Hudayj led 10,000 men in a new major expedition deep into Ifriqiya (The two earlier campaigns which the sources mention probably didn't happen due to the First Fitna and the lack of details on those campaigns). Like the 647 campaign, many major figures of the age were part of the army: Abdallah ibn al-Zubayr, Abdallah ibn Umar, Abd al-Malik ibn Marwan and others. Following the path Abdallah ibn Sa'd had taken into Byzacena, ibn Hudayj established an encampment at Qammuniya, near to the future site of Qayrawan. Ibn al-Zubayr campaigned on the eastern coast, defeating Exarch Nicephorus at Hadrumetum (Sousse) and capturing the city. While Abd al-Malik ibn Marwan campaigned to the northwest, besieging Byzantine forces at Cululis, a strategic fortress controlling mountain passes into the interior. Having dominated most of Byzacena, Ibn Hudayj personally led the whole army north, deep into Zeugitana, past Carthage to the northernmost city of all Africa: Hippo Diarrhytos (Bizerte), some 180 km north of Qayrawan, occupying the strategic port.
Despite these major triumphs, Mu'awiya ibn Hudayj made no effort to render his conquests permanent. Instead he abandoned the entire region and returned to Egypt. This is particularly puzzling as Byzantine control was very weak at that time due to the new tax levies imposed by Constans on the North Africans. Thus, Ibn Hudayj's campaign was just a raid, like that of Abdallah ibn Sa'd two decades prior. Perhaps related to this campaign, was the 666/7 raid of Ruwayfi ibn Thabit and Fadala ibn Ubayd on Gigthis, the isle of Djerba and even Olbia (Sardinia) via Tripoli - now emerging as a centre for Muslim naval forces. There also seems to have been a raid against Sicily around the same time, showing the increasing reach of the Muslim navy. Meanwhile, Uqba ibn Nafi was campaigning in Sirte, Fezzan - taking ancient Germa - and in the Djerid.
However, these victories further emphasized the vulnerability of North Africa and the weakness of the Byzantines on land and sea. They also seem to have played a major role in the assassination of Constans II, who failed to defend Africa, despite being in nearby Syracuse. On another point, it also increased the wealth and prestige of the Marwanid family, not only due to Abd al-Malik's participation but also because Marwan ibn al-Hakam had authorized the expedition on behalf of the caliph Mu'awiya I.