Led by their king, Gaiseric, some 80,000 Vandals, a Germanic tribe, crossed into Africa from Spain in 429. In the following year, the invaders advanced without much opposition to Hippo Regius, which they took after a siege in which Augustine died. After further advances, the Vandals in 435 made an agreement with Rome to limit their control to Numidia and Mauretania. But in 439 Gaiseric conquered and pillaged Carthage and the rest of the province of Africa.

The resulting decline in trade weakened Roman control. Independent kingdoms emerged in mountainous and desert areas, towns were overrun, and Berbers, who had previously been pushed to the edges of the Roman Empire, returned.

Belisarius, general of the Byzantine emperor Justinian based in Constantinople, landed in North Africa in 533 with 16,000 men and within a year destroyed the Vandal kingdom. Local opposition delayed full Byzantine control of the region for twelve years, however, and imperial control, when it came, was but a shadow of the control exercised by Rome. Although an impressive series of fortifications were built, Byzantine rule was compromised by official corruption, incompetence, military weakness, and lack of concern in Constantinople for African affairs. As a result, many rural areas reverted to Berber rule.