The best candidate matching this "King of the Africans" which is mentioned in the "De Carolo Magno" (or "Gesta Caroli Magni") by the monk of St. Gall seems to be one ruler of the Aghlabid dynasty of Kairouan, present Tunisia. The dynasty was governing the Ifriqiya in the name of the Abassids rulers of Baghdad. The King of the Africans sent envoys to Charlemagne, bringing a Marmorian -Libyan- lion and a Numidian bear, with Spanish iron and Tyrian purple. The emperor gave liberal support to these regions, as he knew they were in a constant poverty. Thus the "inhabitants of Africa" kept constantly loyal and obedient to the empire and paid a considerable tribute
North Africa is stretching from Morocco to Western Libya. It's the Maghrib of the Arabs. North Africa, by the Carolingian times, has passed to Islam and Arab conquerors since the 7th century. The native population of this region was the Berbers, an amalgam of the various peoples present in North Africa since the prehistoric times. They were nomads or peasants. The region first passed under the rule of the Phoenician traders who founded settlements along the coast as soon as the 12th century, then Carthage, founded in 800 B.C., as the center of the second wave of Phoenicians. The city founded some more trading posts like Hippo Regius (present day Annaba, Algeria) or Tangiers, in present Morocco. Once Carthage destroyed in 146 B.C as a consequence of the Punic Wars against Rome, the Romans became the new masters of North Africa. The country was the "granary of the empire". Christendom developed. In 429, as the Roman empire was crumbling under the assault of the Germanic tribes, the Vandals conquered the whole of North Africa, taking Carthage in 439. The Vandal kingdom was quickly destroyed by the Byzantine general Belisarius, in 533. The imperial control which was restaured nevertheless remained a pale shadow of what the power of Rome had been in the region, and many rural areas returned to the Berber rule
The next and most important invaders were the Arabs, who brought with them their new faith, Islam. The Arabs had just conquered the Middle East. The first expeditions in North Africa occurred as soon as between 642 and 669, bringing Islam. Such expeditions were of pure local initiative. When the caliphate moved from Medina to Damascus with the dynasty of the Umayyads (661-750) however, the later recognized the strategic necessity of dominating the Mediterranean and they began a concerted military effort in North Africa. In 670, the Arab army of Uqba ibn Nafi established the town of Al Qayrawan (modern Kairouan, Tunisia) and used it as a base for further operations. The conquest pushed westwards in Algeria, with the help of converted Berber auxiliaries, where it was met with a strong opposition of the Christian Berbers. Ifriqiya, generally, was considered by the Arabs a difficult target. Caliph Omar called it 'Moferecca-T-el-Radea,' the 'treacherous distant.' The Arabs also called the area 'Djezirat-al-Maghreb,' the 'Island of Sunset.' North Africa was the first failure in the Muslim conquest, but the Byzantines did not know to take profit of that. It was Okba that actually vanquised over, but it took 33 years to definitively defeat the Roman Catholic Berbers of the mountains and the South. Prince Koceila first defeated and killed Okba and then, about 695 A.D., the Berbers, who had been federated by the Kâhina, Queen of the Djeroua Zenete, of the Aurès region (now Algeria), perhaps of Jewish faith, crushed the Arabs in Tébessa. By 698, the latter were able to take and razed Carthage to the ground, founding Tunis as an arsenal. And, fanning the dissensions among the proponents of the Berber queen, they overtook the Berber in 703 as Islamization took over during the 9th century A.D. The Kâhina had been decapitated in the Roman amphitheatre of El-Djem in 693. Westerners considered it as North Africa's 'Joan of Arc.' The conquest of the whole of North Africa was eventually completed by 711 A.D., Morocco included. Berbers as a whole generally had seen Arabs like more or less acceptable heretics only. Those were the times when the famed episode took place, when Okba, as he had reached the Moroccan shores, had his horse to step into the Atlantic Ocean, proclaiming that he was taking Allah like the testifier that he could not go further into the conquest!
The part of the conquest located from Western Lybia to Eastern Algeria became the 'wilaya' of Ifriqiya. Berbers in the mountainous areas -- like the Kabyles -- or desertic ones -- like the Tuaregs the name of who means 'those abandoned by God [the one of Islam that is]' -- long remained Christians or even practiced a only superficial Islam. Most Christians in Tunisia had chosen to convert and some isolated and vegetating Churches only survived. Gafsa, a caravan city, remained a prosperous city until in the 12th century A.D. as by the 10th century, Latin was still spoken there and peoples were Christian. It seems like, by the way, that a 'natural' delineation, running all along the history of the Maghrib, have been the one being extent from slightly to the West of Bejaia, in the North, to slightly to the West of Biskra, in the South. This 'border' likely is matching the antique difference which existed since long between a part of the Roman 'Africa', with Numidia, on the one hand, and Mauritania, West, on the other hand. Further West, another frontier existed with Mauritania Tingitana, which was to belong to the history of Morocco. Algeria by itself was eventually unified by the Ottoman Turks, by the 16th century, only, as they too reduced Tunisia to its current borders. This Muslim "province" of Ifriqiya was governed from Kairouan by governors appointed by the Umayyad caliphates. The same Berberian tribes which had provided for ancient revolts like Donatism or the Circoncellions, also did for Muslim schisms and heresies. A widespread rebellion of the Berbers, as they were treated like second-class Muslims by the Arabs, brought disorders as populations, albeit islamized, had remained deeply Berberians. The Berbers used the Kharijite Islam -a dissent, egalitarist, legal opinion in the Umayyad empire, like a base, and founded theocratic tribal kingdoms up to Tilimsan (present Tlemcen, Algeria, near the border with Morocco). As it took advantage of the end of the Umayyad Caliphate by the mid-8th century A.D., as it based on a ressentiement of the Berbers little recognized by the Arab conquerors, the kharijite heresy grabed Kairouan for a while. The authority in the Ifriqiya was reestablished by the new dynasty, the Abassids, which had taken the power in Damascus in 750, and had moved the capital to Baghdad. Ibrahim ibn Al Aghlab was apointed the governor in Kairouan. He and his successors -constituting the dynasty of the Aghlabids- actually ruled independently until 909, with their court becoming a center of learning and culture, as, meanwhile, the Ifriqiya still held many Christian bishoprics. So, it is one of those Aghlabid rulers, who is the 'King of the Africans' as quoted in the 'De Carolo Magno.' The Aghlabids dynasty ruled during one century (800-909) on the Ifriqya, ruling on behalf of the Abbasids and paying a toll. It was a dynasty of builders of public and religious facilities and walls. Malekism then prevails in Ifriqya. Kairouan, the capital city to Aghlabids, was first 'al Qarawin,' 'the camp,' and, after the decline of the cities of the North Africa due to the Germanic invasions, it marked, finally, the renewal of urban culture. It was with Fustat, Basra and Kufa (a city in Iraq south of Baghdad), one of the first cities created ex nihilo during the Arab conquest. She was soon given the Grand Mosque and the installation of Islam was so little challenged that walls were not built until 762 to counter Kharijite Berbers' attacks. Kairouan eventually managed to impose itself like the major urban center of North Africa, rich through trade and famous for its intellectual and religious life. His downfall came, in 1057, with the Hilalian invasions
As far as the other parts of North Africa are concerned, this part West of the Aghlabid lands was governed by the dynasty of the Rustumids from 761 to 909. Their 'kingdom of Tahirt' had taken its name from their capital, Tahirt -or Tiaret- southeast of Oran -current western Algeria, as it was founded by Ibn Rustom who was fleeing Muslim orthodoxy. The Rustumid rulers were Ibadi Kharijite imams, elected by leading citizens. The court at Tahirt supported scholarship in mathematics, astronomy, and astrology, as well as theology and law and it welcame numerous scholars from Egypt, Iraq and Persia. As the kingdom eventually stretched from Mascara to Tripolitania, it also was a trade center, between Europe and Africa. Morocco, on the other hand, was governed from 789 to 926 by the Idrisid dynasty. Idris I came from the East, fleeing the new power of the Abassids, and he was the great-great-grandson of Fatima, the daughter of Muhammad. His son, Idris II, made Fès his capital. The arrival at Fès, in the 9th century of two flows of refugees -one from Kairouan, the other from Cordoba, in Spain, started an important center of Islamic and Arab culture. All of North Africa was a country of harbours, cities and coutryside, with important trans-saharan trade routes. Aghlabids like the Idrissids were protectors of science and letters and they endeavoured to imitate the literary and artistic move which occurred at the time in Baghdad. Kairouan and Fès thus turned centers of scholarship where Muslim youth long came to train
It happened that, by the last decades of the 9th century, missionaries of the Ismaili sect of Shia islam, issued from current southwestern Iran, converted the Kutama Berbers of what is now known like the 'Petite Kabylie' region, in center-east Algeria. They waged war against the Sunni governors of Ifriqiya. Kairouan fell to them in 909. The Ismaili imam, Ubaydallah, declared himself caliph and established Mahdia, Tunisia, as his capital. He claimed to descend from Fatima, the daughter of Muhammad and wife of Ali, hence he founded the Fatimid dynasty. In 911, the Fatimids turned to the Rustumids, who were defeated in turn (it is to be noted that they had not organized any reliable standing army). Ibadi Kharijite refugees from Tahirt fled south to the oasis at Ouargla whence in the eleventh century they eventually moved southwest to Oued Mzab, currently Ghardaïa, Algeria. The Fatimids pushed up to the border of Morocco but their main target was the East. They eventually conquered Egypt, in 969, founding the new city of Cairo in 972, the Arabic name of which 'Al Qaira' means 'the victorious one.' Thus, they let the rule of Ifriqiya and most of current Algeria to the Zirids (972-1148), who were a Sanhadjian Berber dynasty (they were Maures who had come from northern Senegal, a region where kingdoms had been founded by the encounter between nomadic Berbers and Black farmers), which had founded the towns of Miliana, Medea, and Algiers. The domains West of this new Ifriqiya were left to the Banu Hammad -or Hammadids- a family branch of the Zirids, who reigned from the 'Qala of the Beni Hammad', in the region of the Hodna, southeast of Algiers. Morocco, as far as it is concerned, was not part of this part of the history of the Maghrib as both Arab and Berber dynasties succeded the Idrisids. Hammadids long conflicted with the Zirids as the Fatimids eventually sent against them Arab beduins from Egypt starting in the first half of the eleventh century, who overcame the area, and definitively arabized Berberian North Africa. Trans-Saharan trade shifted either to Fatimid Egypt or to routes in the West leading to Spanish markets
->Cairo in History
Since the Arab conquest, current Cairo, the capital of Egypt endured a long history. As the Byzantine capital of the era about 650 A.D. was Alexandria, the southern tip of the Nile's delta was overlooked by Babylone of Egypt, a small military post. It was taken by the Arabs by April 641 as Amr ibn el-As, their general, when making his tent folded, ordered to remain standing because a dove have made her nest inside. That tent, in Arabic, 'al Fostat,' remained a landmark as a city developed, with the Amr mosque, which turned the Arabic capital of Egypt as prefered to the Greek, a long way out, Alexandria. Under the Abassids, they founded a new city, El-Askar, more North, of which about nothing was left. The Tulunids, barely more North, founded a new city still, El Qataï. It was the Shiite Fatimids however, with 'Al-Qahira' -- the 'captivating city' in Arabic -- with its magnificent palaces, the Al-Azhar mosque and its walls, which founded the real basis to current Cairo as it was Gawhar, a vizir of Greek origine who had led the army to victory, who served like the architect. Al-Fostat, along the Nile's eastern bank, turned then a potent trade city where merchant ships could reach from the Mediterranean. The city was inhabited often by Jews and Christians, the latter for cause that the Holy Family had made a stop there along the Flight to Egypt. Fatimids in their capital, founded a 'house of Wisdom,' which facilitated the study of Hellenistic science and drew lawyers, medics, astronomers and mathematicians. The Pyramids, located southwest of the Arabic city, as far as they are concerned, as they date back to the oldest dynasties of Egypt, were considered by the Middle Ages people like the corn lofts built by the exiled Hebrew Joseph to counter predicted 7 years of hunger