The Berber kingdom of Mauretania was an amalgamation of the Mauretanians and Numidians of antiquity, which ruled the area roughly corresponding to modern Algeria and Tunisia until 1060, when the Almoravids from the Sahel took control of the entire Maghreb (excluding the Port of Carthage).
Successes against Byzantium
This paragraph has a misleading title, since territorial gains by the Mauretanians against Byzantium were fairly thin on the ground. The Berbers did not have sufficient soldiers to mount massive campaigns and, though the Byzantine governor of Africa didn't either, the only particularly significant acquisitions were those of Algiers (645AD) and Constantine (745AD - the city was renamed after its original Berber title, Cirta.) Other than this, the Berber rulers were fairly impotent; as they had no fleet, sea trade was impossible. Under Berber rule, the Maghreb continued on a steady stagnation.
Arrival of the Almoravids
The borders of Mauretania were always loosely distinguished, with native tribes and nomads always probing between the kingdom and the wilderness beyond. However, in 1060, the government at Fez (the Mauretanian capital) were met with a more definite threat; an invasion of the Berbers from the Sahel. These were of a sterner cast of their brethren in Mauritania and were known as the Al-Murabutin, or Almoravids. At first the Mauretanian king thought little of the incursion - and sent little more than a border force down to intercept it. It was soon clear that greater action was needed, but the Almoravids moved quicker than the Mauretanians, and the latter lacked the military muscle in any case. In the later months of 1060, the Almoravids captured the Mauretanian capital at Fez, and by the February of 1061, the Berber Kingdom of Mauretania had ceased to exist!