Muslim conquest of the Maghreb

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.

In 669, Caliph Mu'awiya appointed the veteran Uqba ibn Nafi to head 10,000 troops in a new campaign to the west. Accompanied by Busr ibn Abi Artat, Shurayk ibn Summayy and Zuhayr ibn Qays, as well as some Berbers. Due to the withdrawal of many Byzantine troops from the Africa to put down the rebellion of Mizizios, Uqba was able to easily occupy all Byzacena without incident, beginning the foundation of Qayrawan as a permanent base of operations in the Maghreb, in contrast to the ephemeral policies of his predecessors. For the next 5 years, he devoted his attentions to the building of this new garrison town, without launching expeditions against the Byzantines or Berbers. The lack of campaigning seems to have been the cause of Muawiyah removing Uqba, placing the Maghreb under the control of Maslama ibn Mukhallad - the governor of Egypt - who appointed his non-Arab (perhaps a Copt, Greek or Berber) freedman Abu al-Muhajir Dinar as governor of Ifriqiya.

Abu al-Muhajir disliked Qayrawan, and a few kilometres to the north founded a new city named Takirwan, which means 'place of assembly' in Berber.The choice of the Berber sounding name was part of Abul Muhajir's new policy of rapprochement of the Berbers. He was able to skillfully win over many Berber tribes in the Gafsa region and begin converting them to Islam. Recognising the numerical inferiority of the Muslims compared to the vastness of the Maghreb, he sought to enlist the Berbers en masse to assuage such concerns. He then conquered Cape Bon and much of Zeugitana. In 678 he unsuccessfully besieged Carthage, but was able to get a treaty out of them, probably recognising the Muslim control of Byzacena in exchange for Muslim withdrawal from Zeugitana. This treaty allowed him to focus his attentions on the west, pushing deep into Numidia. For the next 2 years he established himself at Tlemcen, or more likely a placed called Lamis around the northern foothills of the Aures (perhaps Lambaesis, Lamasba or Ksar Bellezma). Here he campaigned to Milev - dangerously close to the Numidian capital of Constantine - and continued his rapprochement policy with the Berbers, as he had done previously in Gafsa. This bore fruit in a major way through the conversion of Kasila, the most powerful Berber leader in the Maghreb, based at Tlemcen or more probably Tubna. Kasila then accompanied Abul Muhajir back to Takirwan.

Uqba's Campaign

Soon after Abu al-Muhajir's victories, his benefactor Maslama ibn Mukhallad died, and the new Caliph Yazid I reinstated Uqba. Accompanied by some 5–10,000 troops and 25 of the Sahaba, Uqba returned to the Maghreb in 682. Upon his arrival, he arrested Abul Muhajir and Kasila, moved the capital back to Qayrawan - leaving Zuhayr ibn Qays as its governor - and took a more uncompromising and forceful approach with the Berbers in contrast to the policies of Abu al-Muhajir.

Then he embarked on his grand campaign to the west, with around 15,000 troops and both Kasila and Abu al-Muhajir in chains. This wasn't a mere heroic and dashing raid as it has been remembered. Instead, it was intended to destroy the manpower, resources and reserves of the Byzantine interior, since Muslim control over Byzacena and Zeugitana was insecure as long as the Byzantine positions in Numidia weren't neutralised, and only then could the final campaigns against Carthage and the coasts begin. Beyond that, the Byzantines had strongholds and troops much further south and west into Algeria than previously realised; far from the coasts, deep into Sitifensis. So the Muslims faced a much greater obstacle, which partly explains why the conquest of the Maghreb took so long.

From Qayrawan, Uqba likely marched west through the Kasserine Gap to ancient city of Ammaedera, then past Byzantine command post of Meskiana to the stronghold of Bagai overlooking the Numidian plains. Here the Muslims met stiff resistance and were unable to take the city. Abandoning the siege Uqba continued west avoiding sieges of formidable strongholds such as those around Constantine. Instead focusing on a more sweeping strategy through the open country outmanoeuvring his foes, maximizing the impact of his limited men and resources. The difficult terrain of the Algerian coast - where the Byzantine navy could intervene - was avoided, and nothing is mentioned about the ancient cities of Cuicul, Caesarea, Setif and Tipasa in any source.

After Bagai he raided Lamis(perhaps Lambaesis, Lamasba or Ksar Bellezma) until reaching the westernmost Byzantine fortress: Zabi Justiniana (Bechilga, M'sila). Here he broke the back of Byzantine resistance, vanquishing their last strength. Retreating to their fortresses, they avoided more open battle and ceded the entire countryside to the Muslims. After the decisive victory, Uqba continued his plunge westwards to Tahert defeating yet another force and then further to Tangier where he met Count Julian who redirected him southwards deeper into Morocco. At the ancient city of Volubilis (abandoned by the Romans in 285) he defeated some local Berbers, before venturing southwards to the Atlas mountains, to regions the Romans had never conquered. He seems to have first pursued some fleeing Berbers all the way to the Draa before doubling back and besieging the city of Aghmat near Marrakesh. He then traversed the Atlas once more and campaigning throughout the Sus, until his tireless 2,000 km advance was checked at Agadir by the Atlantic Ocean. Spurring his horse into its endless waves, he proclaimed:

يا رب لولا أن البحر منعني لمضيت في البلاد إلى مسالك القرنين مدافعًا عن دينك مقاتلًا من كفر بك

O lord, if my course were not stopped by this sea, I would still go on, like Dhul Qarnayn, defending your faith and fighting those who worship other gods than thee.

However, some modern scholars doubt if Uqba ever reached as far west as Tangier, let alone Sus al-Adna and Sus al-Aqsa due to the immense distance away from Qayrawan.

Yet, as Gibbon puts it, this Mahometan Alexander, who sighed for new worlds, was unable to preserve his recent conquests. At some point during the western advance, Kusaila had managed to get free, his mistreatment by Uqba led him to rescind his allegiance to the Muslims, now making common cause with the Byzantines. (However, the nomads of the Zenata south of Tlemcen and the Aures desert fringe, remained allied to Uqba). Kusaila used the strategic Byzantine stronghold of Tobna, former seat of the Comes of Africa, as his base of operations. Instead of attempting a risky pursuit, he allowed the Muslims to continue their advance far to the west, preferring to lie in wait and prepare an ambush for Uqba's return journey. Until at Tahuda he and his Byzantine allies surprised the returning Uqba and at the Battle of Vescera the entire Muslim army was annihilated. The nearby city of Sidi Okba houses Uqba's tomb and serves as a memorial to the event.

Battle of Mamma

In wake of the disaster at Tahuda combined with the outbreak of the Second Fitna, Uqba's deputy at Qayrawan, Zuhayr ibn Qays, was obliged to abandon the city and retreat all the way to Cyrenaica. Allowing Kusaila to enter Qayrawan unopposed, there he made treaties with the Berber Muslims and the few Arabs who stayed behind. For the next few years he ruled most of Byzacena and Numidia, perhaps with some tacit Byzantine approval, though he was no puppet.

In late 684 the Umayyads regained Egypt from the Zubayrids, and a few years later in 688/9, Caliph Abd al-Malik ibn Marwan had consolidated enough to send Zuhayr ibn Qays to defeat Kusaila and retake Qayrawan. Upon hearing of the approach of Zuhayr and his army of 4,000 Arabs and 2,000 Berbers, Kusaila abandoned the unwalled Qayrawan in favour of a more strategic position in the mountains. At the Battle of Mamma (in the Aures or perhaps at Henchir-Ed-Douamès) the Muslims defeated and slew Kusaila. Regarding this, Hugh Kennedy states: As so often, it is difficult to see reasons for the military success of the Muslim forces over what was probably a much larger army, well acquainted with the terrain. We can only observe that, once again, when it came to crucial battles, the Muslim forces proved superior.

Zuhayr took Sicca Veneria, Thysdrus, and Laribus, and then proceeded to chase the remnants of Kusaila's forces as far west as the Moulouya River on the border of Mauretania Tingitana. By this, the last vestiges of effective resistance in the west had been quashed and the region was ripe for conquest. Though without a navy, the Byzantine coastal cities remained outside his grasp. Soon after such victories, Zuhayr had to suddenly abandon the region, due to a Byzantine fleet landing in Cyrenaica in 690. On his westerly advance against Kusaila, Zuhayr hadn't left enough troops behind to garrison Cyrenaica, enabling the Byzantines to invade the province. Now for the first time since its conquest by Amr ibn al-Aas half a century earlier, Barqa had fallen out of Muslim control. This posed an existential threat to the Muslim position in Ifriqiya, as the Byzantines could cut the line of communication with Egypt, and potentially even threaten Egypt itself. In the event, Zuhayr was defeated and slain by the Byzantines in Cyrenaica, meanwhile the Second Fitna was still raging, denying any immediate action by the Caliphate. As such, this was the low point of the Muslim conquest in the Maghreb. However, the Byzantines lacked the will or resources to follow through on their victory, and the final campaign was soon to begin.

Third Invasion

By 694 Abdalmalik had won the civil war, consolidated the Caliphate and now had the manpower and resources to deal with Ifriqiya once and for all. Beyond that, 29 years prior he'd personally campaigned in the region, so had a direct idea of the region's needs and challenges. Thus he sent Hassan ibn al-Nu'man with a huge force of 40,000 troops. The recent naval assault on Cyrenaica brought the Byzantine threat back to the forefront, while Abul Muhajir, Uqba and Zuhayr's campaigns in Numidia reduced the western threat, allowing forces to concentrate on Carthage and the Byzantine coast.

Reinforced en route by Luwata Berbers, Hassan made directly for Carthage. Upon seeing the size of the Muslim army the inhabitants decided to abandon the city, fleeing to Sicily and Spain, allowing Hassan to enter the Exarchate's capital unopposed in 695/6. The new Byzantine Emperor, Leontius, was furious at such cowardice, a large fleet was sent, bursting through Carthage's harbour chain, defeated the Muslim garrison, retaking the city, La Goulette and other nearby towns - allegedly committing much plunder and atrocities. The Byzantine reconquest proved short-lived. Met by an enormous fleet sent by Abdalmalik, the Byzantines, rather than fight, evacuated, fleeing to Crete where they mutinied against Leontius, elevating Aspimar to the throne as Emperor Tiberius III. The city fell to Hassan after a siege, he ordered its destruction: walls demolished, harbour filled in and every trace effaced. Just as the Romans themselves had done some 844 years prior. This is only example of the abandonment of a provincial capital anywhere in the caliphate. The city's nearly thousand-year history as the capital of Africa, under successive Punic, Roman, Vandal, and Byzantine regimes, finally came to a definitive close. Its ruins were to be used to build nearby Tunis, and even as late as the mid 10th century, its columns were procured at great expense for Madinat al-Zahra, Cordoba. With Carthage in Muslim hands, the Byzantine military leadership likely shifted operations temporarily to either Ceuta or Sardinia, while Christian resisters fled throughout Zeugitana, such as Satfura, Mornag and Clypea on Cape Bon. Hassan defeated them at Bizerte and then at Beja, while Berber forces fled to Hippo Regius (Annaba).

The Romans defeated, the Muslims now directed their attentions to the Berber interior, where a new powerful force had risen under the command of al-Kāhina (the prophetess) based in the eastern Aures. Either Christian or Jewish, she seems to have had some connection to Kusaila and perhaps was married to a Byzantine, though it is improbable that she had any alliance or coordinated strategy with the Byzantine Empire itself. Hassan marched through Theveste, camping at the river Nini, 29 km from the important city of Bagai, which had bested Uqba over a decade earlier. But Kahina reached the city first, razed its walls, lest the Muslims use it as a fortified base of operations, and marched towards the Muslims. At the Battle of Meskiana the Muslims were badly defeated; Kahina pursued them for over 300 km to Gabes, capturing many of their soldiers including 80 Arab nobles, while Hassan retreated to Tripolitania or Cyrenaica.

For the third time, Ifriqiya had been lost. However, in contrast to Kusaila's strategy a decade and a half earlier, Kahina chose not to enter Qayrawan, leaving it under Muslim control, possibly to avoid an immediate war of revenge. Believing the Muslims were only interested in plunder, she is said to have implemented a scorched-earth policy and mass deforestation, devastating the region to remove any incentive for further invasion. However this policy backfired, as it turned much of the sedentary Romano-African population against her, who then appealed to the Muslims to assistance. After a few years in the east, the Caliph sent Hassan reinforcements and he relaunched his campaign. Defeating Kahina at Gabes, the Muslims pursued her westwards towards the Aures, where she was slain and her forces crushed in a battle around 701 at a location historians dispute (Garaet et Tarf (north of Bagai) or Tabarka or Tobna). Afterward, Hassan then revived Abul Muhajir's policy of reconciliation, recruiting and converting 12,000 of Kahina's followers, including her two sons. Soon after, the ancient port of Hippo Regius (Annaba) fell to the Muslims.

Finally, after half a century, the long conquest of Byzacena, Zeugitana and Numidia was complete. Hassan returned to Qayrawan and began to formalize Muslim rule, setting up a government based on Umayyad administrative norms, establishing the diwan to manage troop finances, a chancery and enforcing the Kharaj tax on the Christians. He also set about founding the new garrison city of Tunis, which unlike the exposed Carthage, was shielded from Byzantine naval raids by its inland location, while remaining accessible to the sea via a canal he built through the lagoon. In 702 Abd al-Aziz ibn Marwan, viceroy of Egypt, sent a thousand Coptic shipwrights to build a new dockyard and build 100 new warships, extending Muslim naval influence to the central and western Mediterranean.

Musa ibn Nusayr

In 704/5 Abd al-Aziz, dismissed Hassan and replaced him with his own protégé, Musa ibn Nusayr. Part of this was a dispute over the jurisdiction of Cyrenaica and Tripolitania, where Abd al-Aziz appointed his own governor. But this was also part of the growing rift between Abd al-Aziz and his brother, the Caliph Abd al-Malik. Abd al-Aziz sought to assert his own authority, as well as that of Egypt, over the Maghreb. He seems to have also wanted more revenue, as shown by his confiscation of all of Hassan's wealth and even gifts intended for the Caliph.

Thus he appointed his own man, Musa ibn Nusayr. The two had worked together for the last twenty years, ever since Caliph Marwan appointed Musa as an advisor to Abd al-Aziz. As such Musa could be trusted to enact Abd al-Aziz's policies in the west. Accompanied only by a few volunteers from Egypt, Musa had to depend on the Arab troops already available in Ifriqiya, and needed to continue the rapprochement and recruitment policies towards the Berbers that his predecessors had enacted. Though he did have some able commanders: Busr ibn Abi Artat, Abd al-Rahman ibn Abi Salama (grandson of Abd al-Rahman ibn Awf), Uqba's sons: Abu Ubaydah, Iyad and Uthman, Abu al-Muhajir's son Sulayman, Ayyash ibn Akhyal, as well as his own four sons.

He continued the naval build up of Hassan, and made sure to prevent contact between Romano-Africans and the Byzantine naval forces. Using the newly built arsenal of Tunis to send campaigns throughout the central and western Mediterranean. In 704/705 Ayyash ibn Akhyal raided Sicily, plundering its capital Syracuse. In 706 the Balearics were raided and again in 708 by Musa's son Abdallah. Sardinia was raided every year from 706 to 710 and the Muslims seem to have some partial occupation of the island, particularly around Cagliari, until 732, since papal reports mention Liutprand, King of the Lombards negotiating with the Muslims for the bones of St. Augustine.

On land, Musa began his campaigns with an assault on a Berber fortress near Qayrawan named Zaghwan. He then campaigned in the Aures of southern Numidia, campaigning as far as Tubna. Few details exist regarding these campaigns, but they seem to have focused on gaining as much booty as possible, both plunder and especially captives, so as to clear his name of past financial misdeeds in Basra, and to prove he was no less capable than Al-Hajjaj ibn Yusuf, his accuser.

To the north stood the great fortified strongholds in the central Numidia's highlands, chiefly Cirta (Constantine) the Roman provincial capital. Yet, the sources mention nothing after Abul Muhajir and Uqba's campaigns around Mila, over two decades prior. Beyond this point no organized Byzantine resistance can be traced and only scattered local opposition remained.

Even so, the challenges the Muslims faced were significant: The harsh terrain of the Constantinois region, coupled with its fertile land worthy of defence, blunted Muslim mobile warfare and left them prone to ambushes in mountain passes. To individually reduce each and every fortress in such conditions would have called for a huge investment of time, resources and manpower which the Muslims could not spare. But, the mountains also served to work against the defenders, isolating them from one another, while the loss of Carthage made any attempt at external support from, or even communications with, Byzantium very difficult. Thus the region never became a major hub of resistance. The Muslims, unwilling to bleed themselves in mountain passes, advanced as negotiators rather than besiegers. Bypassing the fortresses, they focused on trying to win over the local inhabitants and leaders, eventually with the hinterland in Muslim hands, the Numidians acquiesced and made terms with the Muslims. Though, that Constantine retains its name until today shows that it retained some of its Byzantine identity.

Similarly unknown is the fate of the Algerian coastal cities, such as Caesarea capital of Mauretania Caesariensis, Icosium(Algiers), Oran and many others, is unknown.

From Numidia, Musa ibn Nusayr pushed to the far west, following the path Zuhayr ibn Qays had taken to the Moulouya River. Moving into the Fes region, he clashed with Awraba Berbers of Sajuma, where Uqba's sons avenged their father. Thereafter he sent two campaigns to the far south, into the Sus al-Aqsa, one led by his son Marwan, the other by a Berber, Zur'a ibn Abi Mudrik. While they pushed south, Musa personally conquered Tangier, then proceeded to campaign in the Sus al-Adna, before advancing to the Draa valley and the oasis of Tafilalt on the edge of the Sahara. No details exist regarding the conditions or political structures Musa encountered on his westerly advance.

However, at the city of Ceuta his advance was checked by Count Julian, unable to take the city, Musa concluded a peace treaty with Julian, allowing the Count to retain his position in exchange for the payment of a tribute to the Muslims. Julian seems to have been under Visigothic influence. The last definitive reference to Ceuta as a Byzantine possession is from 641 as exile for Byzantine treasurer Philagrius. After the fall of Byzantine Carthage, the Byzantine navy may have briefly moved to Ceuta for a few years - perhaps using it to raid the Visigothic mainland around Murcia sometime between 698 and 702 - but soon after they transferred to Cagliari in Sardinia. In wake of this, the Visigoths appear to have taken over Ceuta, echoing their brief seizure of the city under Theudis in 533.

From there, Musa began large scale conversion and recruitment efforts. The relative absence of Christianity in the central and western Maghreb - where no churches have yet been found and polytheistic ancestor worship, particularly the cult of the ram, predominated - facilitated widespread conversion, to such an extent that the sheer scale of conversion and mass recruitment of the Berbers in unmatched anywhere else in the Islamic world.

In 708 after establishing a garrison at Tangier and beginning the consolidation of the west, Musa returned to Qayrawan with most of the Arabs. Tariq ibn Ziyad, his Berber freedman, was left as governor of Tangier, along with 12,000 Berbers and 27 Arabs to teach them Islam. Such an appointment was significant, marking the first known instance of a non-Arab holding such a high position in the army.

After seven turbulent decades of ceaseless back and forth, the tide of conquest finally covered North Africa, from Cyrenaica to the shores of the Atlantic. Though it may have been achieved sooner, had the Muslims followed Abul Muhajir's rapprochement policy from the start.

Aftermath

With the conquests complete, the Muslims set about ruling the Maghreb. Governing an area more than five times larger than Byzantine Africa, and double that of the Roman empire at its height, the Caliphate couldn't rule as their predecessors had done, they needed to connect peoples and regions who had never before been united, and would never again be thereafter.

Governance was easier in "Byzantine Africa" (Tripolitania, Tunisia and Numidia), as one of the most urbanised, fertile and prosperous regions of the whole Mediterranean, they could rely on the infrastructure left to them by almost a millennium of previous empires. But beyond Sitifensis, in "Berber Africa", the situation changed drastically. Of the vast region, only the small coastal region had ever seen centralized imperial rule, and that was centuries prior, the remainder had never before been subjected. Sparsely populated, largely pastoral or subsistence farming, with few major urban centres, the Muslims were dependent on the support of Berbers.

The region had become its own province distinct from the rule of Egypt in 705, divided into 5 provinces: Ifriqiya (Zeugitana and Byzacena), Tripolitania, Zab (Numidia), Near Sus and Far Sus. Of the 50,000 Arab troops garrisoned in the Maghreb, the majority were in the east, as shown by Ifriqiya's subdivision into many kura. But in the much larger west, the only garrisons were Tlemcen, Tangier and the unlocated Tarqala. Here local support was crucial, and with every mile westwards the importance of Berber manpower increased.

These Berber soldiers formed the backbone fuelling the new surge of conquest throughout the west. In 710, just two years after the fall of Tangier, Berber commander Tarif ibn Malik began the first incursions into Iberia; the following year Tariq ibn Ziyad led 12,000 men, mostly Berbers, across the strait.

One motive for this campaign was to redirect growing tensions already beginning in Tangier between the garrison and the local population. The diverse composition of the troops - Berbers from various tribes and regions, as well as the black troops(Sudan) recruited during the Sus al-Aqsa campaigns - likely created significant friction. Compounding the issue, since a regular system of payment was likely not yet in place for these new converts, Tariq had to quickly find a source of revenue if they were to stay loyal. Successfully channelling the energies of these new troops, Tariq managed to take most of Iberia, their role is reflected in archaeological findings: of the 190 skeletons at the mid 8th century Muslim cemetery of Plaza del Castillo Pamplona, almost two-thirds of the men were of Northeast Moroccan origin and twelve were of sub-Saharan origin.

They also constituted a large minority of the troops in the campaigns against Sicily and Sardinia, which regained new vigour from 720 onward. Yet even as armies were pushing deep into Frankia and the central Mediterranean, the Maghreb itself had not been entirely consolidated. As late as 736 campaigns were still being sent into the Sus, and pushing even further south into the "Land of the Blacks" in pursuit of gold.

The Great Berber Revolt

Initially, the new Berber converts were treated essentially as if they were Arab, and the Caliphate made efforts to teach them Islam, reaching its zenith under Caliph Umar ibn Abd al-Aziz who sent 10 scholars of the tabi'een to teach throughout Maghreb, but with millions populating the enormous region, much more was required. Nevertheless, it is reported that the majority of Berbers embraced Islam through the efforts of Umar II's governor, Ismail ibn Ubayd Allah ibn Abi al-Muhajir (718–720), making them the first non-Arab group to convert on such a mass scale.

However, the reforms of the short reign of Umar II were quickly discarded by his successors who began to implement discriminatory policies such as imposing the Jizya upon the Berbers, exacting it through both monetary collection and enslavement. In response the Berbers almost immediately assassinated the governor, Yazid ibn Abi Muslim. Due to their military strength, which the Caliphate was dependent upon, the Berbers were able to get away with this killing and forced the new Caliph to acquiesce to their demand of equal treatment. For the next decade the province enjoyed calm, until 734 with the appointment of Ubayd Allah ibn al-Habhab - provoker of the first Coptic revolt of 725 - who reinstated the discriminatory policies, most egregiously the slave tribute. Despite the continuous obstacles put in their way, the Berbers continued enthusiastic adherence to Islam, though now gravitating to the egalitarian and anti-Umayyad Kharijite movement.

Through his short-sighted policies, Ibn al-Habhab was sowing not only his own undoing, but that of the whole Umayyad Caliphate. The enormous numbers of Berbers which had been recruited, trained and armed by the Caliphate over the last few decades were now to be its downfall. In 740, Maysara al-Matghari, who had likely served in the caliphal armies, began the Great Berber Revolt. By late 742 they'd annihilated several Arab armies, killing many tens of thousands of them, and had occupied as far as great naval base of Tunis, until their defeat near Qayrawan. Thus, after only some 30 years of Arab rule, Morocco and most of Algeria had permanently left the caliphate. Despite the setback at Qayrawan, through their killing of at least 18,000 Syrian Yamani troops they'd undone the balance between the Yaman and the Qays, forcing the former to take drastic measures by murdering Caliph al-Walid II, setting in motion the collapse of the entire Umayyad Caliphate.

In 757, exploiting a Fihrid civil war, the Warfajuma Berbers managed to successfully capture Qayrawan, capital of the Maghreb, rendering the decades long Arab conquest of the Maghreb almost entirely undone. After almost 5 years, the new Abbasid Caliphate sent an enormous force of 40,000 Arabo-Khurasani troops, almost a third of the whole Caliphal army (which played a role in the difficulties in putting down the revolt of Muhammad al-Nafs al-Zakiyah) to reconquer the west. Defeating Abu al-Khattab causing Ibn Rustam to flee west to Tahert, establishing the Rustamid dynasty. Less than a decade later, the Berbers once more bested the foreigners, recapturing Qayrawan in 771. In response, the Abbasids rallied the largest army ever sent west, 60,000 troops, under Yazid ibn Hatim al-Muhallabi, one of the Caliph's closest and most trusted men. With this, the Kharijites were defeated and would never again make an attempt on Qayrawan. Finally, a century after its founding, the city remained securely in Arab hands. Yet, despite the huge numbers (further reinforced in 795, for a total of 130,000 men, mainly from Khurasan almost 5,000 km away) and resources of the Abbasids, they would prove unable to push beyond Numidia - which was itself difficult to control and whose Kutama Berbers would later give rise to the Fatimid Caliphate.

Consequences

Effects on the power structure in the Mediterranean region

The loss of Africa was a severe blow to the Byzantine Empire. In 698, after Egypt, the second large granary and a significant source of taxes went here was lost, which in retrospect did not detract from the empire's ability to survive, but significantly impaired the decades-long defensive struggles against the caliphate. Financially, the lost tax revenue for Eastern Rome/Byzantium could not be compensated for a long time.

The fall of Carthage brought Tiberios the imperial throne, for his officers, afraid of being held responsible for the defeat, elevated him to the position of anti-emperor and overthrew Leontios, who had his nose cut off. Another effect was that there were no longer any major Latin or Romance-speaking provinces in the Byzantine Empire and Greek finally prevailed.

With the conquest of Carthage, the Arabs laid the basis for domination of the western Mediterranean, since they could now use the African ports there as a springboard for operations against the Balearic Islands, Sardinia and Sicily. They also prepared for the invasion of Spain 13 years later by eliminating the flank threat. The capture of Septem, in turn, removed the last immediate obstacle.

Islamization and Arabization of the Maghreb

On the territory of the Exarchate of Carthage, after the conquest, a rather gradual but ultimately complete Arabization of the Latin and Punic speaking population began. Contrary to widespread opinion, the Latin language did not disappear promptly or completely from the Maghreb, which can be read both from Latin grave inscriptions dating back to the eleventh century and from the numerous and conspicuous Latin foreign words in today's Berber languages on site. But the special features of the dialects of Maghrebi Arabic that developed after the conquest were also shaped primarily in the lexis of Latin. The same applies to Christianity in the Maghreb, which did not end with the Arab conquest, but is also documented afterwards by sporadic sources.

In what is now Tunisia, for example, Muslims were probably in the majority towards the end of the ninth century. The decline of Christian institutions only accelerated towards the end of the eleventh century; individual communities survived until the 14th century, after which trace of them was lost. The only thing that is certain is that at the beginning of French colonial rule in the Maghreb there were no longer any Romance-speaking or Christian communities. This ultimately complete Islamization of the entire population brought about the separation of the Mediterranean region into northern and southern halves, which continues to this day.

The full Islamization of the Maghreb along with the full Arabization of the non-Berber population may have been favored by the following factors:

• the still Neo-Punic and thus also Semitic mother tongue of parts of the population,
• possibly remaining Donatist ideas in Christian communities, whose martyristic and theocratic demands as well as rejection of Greco-Roman civilization were fulfilled by Islam,
• possibly remaining Arian ideas in Christian communities, whose anti-Trinitarian demands were fulfilled by Islam
• the fragmentation of the Church in Africa, which was also partly visible to the outside world
• Promotion of Arabization and Islamization given the exposed location of the Maghreb during the Spanish Reconquista and the conquests of the Norman ruler Roger II.

Christianity after the conquest

Archaeological and scholarly research has shown that Christianity existed after the Muslim conquests. The Catholic church gradually declined along with local Latin dialect. According to a view, Christianity in North Africa effectively continued a century after the Muslim conquest but that neither the Church nor the ruling Byzantine veneer was able to resist the propagation of Islam, particularly since they were at odds with each other, and that without any particular persecution on the part of the Muslim rulers, who treated the Christians leniently because they were "People of the Book". Had the first Muslim conquerors persecuted the North African Christians rather than tolerating them, Christianity may well have continued to flourish.

Many causes have been seen as leading to the decline of Christianity in Maghreb. One of them is the constant warfare, as well as persecutions. In addition, many Christians migrated to Europe. The Church at that time lacked the backbone of a monastic tradition and was still suffering from the aftermath of heresies including the so-called Donatist heresy, and this contributed to the early obliteration of the Church in the present day Maghreb. Some historians contrast this with the strong monastic tradition in Coptic Egypt, which is credited as a factor that allowed the Coptic Church to remain the majority faith in that country until about the fourteenth century despite numerous persecutions. In addition, the Romans were unable to completely assimilate the indigenous people like the Berbers.

Local Catholicism came under pressure when the Muslim fundamentalist regimes of the Almoravids and especially the Almohads came into power, and the record shows persecutions and demands made of the local Christians of Tunis to convert to Islam. Reports still exist of Christian inhabitants and a bishop in the city of Kairouan around 1150 – a significant report, since this city was founded by Arab Muslims around 680 as their administrative center after their conquest. A letter from the 14th century shows that there were still four bishoprics left in North Africa, admittedly a sharp decline from the more than four hundred bishoprics in existence at the time of the Arab conquest. The Almohad Abd al-Mu'min forced the Christians and Jews of Tunis to convert in 1159. Ibn Khaldun hinted at a native Christian community in 14th century in the villages of Nefzaoua, south-west of Tozeur. They paid the jizya and had some people of Frankish descent among them. Berber Christians continued to live in Tunis and Nefzaoua in the south of Tunisia until the early 15th century, and "[i]n the first quarter of the fifteenth century, we even read that the native Christians of Tunis, though much assimilated, extended their church, perhaps because the last of the persecuted Christians from all over the Maghreb had gathered there."

Another group of Christians who came to North Africa after being deported from Islamic Spain were called the Mozarabs. They were recognised as forming the Moroccan Church by Pope Innocent IV.

Another phase of Christianity in Africa began with the arrival of the Portuguese in the 15th century. After the end of Reconquista, the Christian Portuguese and Spanish captured many ports in North Africa.

In June 1225, Honorius III issued the bull Vineae Domini custodes, which permitted two friars of the Dominican Order, named Dominic and Martin, to establish a mission in Morocco and look after the affairs of Christians there. The Bishop of Morocco, Lope Fernandez de Ain, was made the head of the Church of Africa, the only church officially allowed to preach in the continent, on 19 December 1246 by Pope Innocent IV. Innocent IV asked the emirs of Tunis, Ceuta and Bugia to permit Lope and Franciscian friars to look after the Christians in those regions. He thanked Caliph al-Sa'id for granting protection to the Christians and requested to allow them to create fortresses along the shores, but the Caliph rejected that request.

The bishopric of Marrakesh continued to exist until the late 16th century and was borne by the suffragans of Seville. Juan de Prado had attempted to re-establish the mission but was killed in 1631. Franciscan monasteries continued to exist in the city until the 18th century.