The Vandals under Genseric conquered the Islands sometime between 461 and 468 during their war on the Roman Empire. However, in late 533 or early 534, following the Battle of Ad Decimum, the troops of Belisarius re-established control of the islands for the Romans. Imperial power receded precipitately in the western Mediterranean after the fall of Carthage and the Exarchate of Africa to the Umayyad Caliphate in 698, and in 707 the islands submitted to the terms of an Umayyad fleet, which allowed the residents to maintain their traditions and religion as well as a high degree of autonomy. Now nominally both Byzantine and Umayyad, the de facto independent islands occupied a strategic and profitable grey area between the competing religions and kingdoms of the western Mediterranean. The prosperous islands were thoroughly sacked by the Swedish Viking King Björn Ironside and his brother Hastein during their Mediterranean raid of 859–862.

In 902, the heavy use of the islands as a pirate base provoked the Emirate of Córdoba, nominally the island’s overlords, to invade and incorporate the islands into their state. However, the Cordoban emirate disintegrated in civil war and partition in the early eleventh century, breaking into smaller states called taifa. Mujahid al-Siqlabi, the ruler of the Taifa of Dénia, sent a fleet and seized control of the islands in 1015, using it as the base for subsequent expeditions to Sardinia and Pisa. In 1050, the island’s governor Abd Allah ibn Aglab rebelled and established the independent Taifa of Mallorca.