Iberia was already out of Rome's control before Rome fell.
In the latter days of the Roman Empire, Iberia was split into five provinces --
- Tarraconensis (northeast)
- Gallaecia (northwest)
- Lusitania (west)
- Baetica (south)
- Carthaginensis (center & southeast)
The Alans, Swabians & two Vandal groups (Silingian & Asdingian Vandals) who jointly swarmed into the Roman Empire in 406 ended up settling in Iberia c.409. They partitioned the peninsula between them by lots: the largest tribe, the Alans, got the lion's share, taking Lusitania and Carthaginensis, the Silingian Vandals got wealthy Baetica, while the Swabians and Asdingian vandals were huddled into the mountainous Galicia & western Tarraconensis (Asturias).
The Visigoths, with a Roman warrant, came in 415 to deal with them all. They practically exterminated the Alans & Silingian Vandals. The Swabians & Asdingian Vandals were sufficiently shielded by their mountains to survive the onslaught. The Visigoths didn't stick around after that campaign, but returned to Gaul. After their departure, the Swabians descended from the hills and expanded their domains southwards into central Lusitania. The Asdingian Vandals descended south into Baetica & southern Lusitania, absorbing the remnants of their Silingian cousins and the Alans. Their new kingdom, known as "Vandalusia", covered roughly modern Andalusia & Algarve.
Although they fended off a few lackluster Roman attempts to dislodge them, the (Asdingian) Vandals realized their position in wide plains of southern Spain was not very defensible. Should the Visigoths & Romans make a serious effort, they would likely meet the same fate as the Silingians & Alans. So, in 428, the Vandals took up an offer from the rebel Roman governor Bonifacius of North Africa and moved out of Spain
en masse for Africa.
Only the Swabians remained in Iberia. By deft negotiation, they managed to secure recognition of Rome as a Germanic kingdom within the empire with their capital at Bracara Augusta (Braga). The Visigoths (in the meantime) had settled in southern Gaul. So, the remainder of Iberia (southern Lusitania, Baetica, Carthaginensis & Tarraconensis), remained in the hands of local Romano-Hispanic lords.
But the Swabians behaved naughtily and began stretching over their prescribed borders. So, in 456, Rome sent the Visigoths in again to teach them a lesson. The Swabians were crushed at the Battle of Urbicus River. But the alarming depradations of the Visigoths prompted the powerful Roman general Ricimer (himself a Swabian) to undertake a coup back in Rome. Ricimer's coup prompted the Visigoths to break off their assault on the Swabian kingdom and return to Gaul to deal with him, leaving behind only a few military governors in the border strongholds (e.g. Lisbon, Coimbra & Orense).
The Swabian kingdom collapsed into feudal anarchy thereafter, as Swabian pretenders, Romano-Hispanic populists & Visigothic governors fought for control of the kingdom. The Visigoth armies returned and gradually restored law & order, imposing a puppet on the Swabian throne in 465.
But the sudden death of the energetic Visigothic king Theodoric II in 466 prompted a Swabian uprising. The Visigoths launched their third (& perhaps most brutal) campaign against the Swabians, driving them out of the Lusitanian lowlands & back up into Galicia. The Swabians miraculously survived this onslaught again. But this time around, rather than withdraw back to Gaul, the Visigoths decided to stick around & permanently settle in Iberia. They didn't need permission from Rome to do so because, by then, Rome had fallen. So all of Iberia, was thereafter in Visigothic hands -- except for the moribund Swabian kingdom in Galicia, which was half-in-vassalage & half-at-war with the Visigoths.
In 507, the Visigoths were defeated by the Franks at the Battle of Campus Vogladensis and lost all their French territories (save Narbonensis/Septimania). The Visigoths were now confined to Iberia. Their capital was transferred from Toulouse to Narbonne and then finally to Toletum (Toledo) in 534.
However, the Visigoths ruled badly. For the first half-century, Visigothic attentions had been focused on their French dominions, They never really managed to impose their control over the advanced Romano-Hispanic cities of the southern Spanish coast. These Romanized cities managed to eke out a sort of semi-independence, retaining their ties to the remnants of the Roman empire across the sea while playing lip-service (if that) to the Visigothic king. When the Byzantines reconqered North Africa from the Vandals in 534, the ties were strengthened.
In 551, the Byzantines launched a concerted offensive in the western Mediterranean, hoping to displace the Ostrogoths from Italy and the Visigoths from Spain. In 554, Byzantine troops landed in Spain. The Byzantines had banked on a general Roman-Hispanic uprising against the Visigoths, but this didn't materialize. They were limited to holding a stretch of coast in southern Spain, stretching from Gades (Cadiz) to Denia (Alicante), and reaching inland only as far as Corduba (Cordoba):
The Byzantine invasion had put the Visigoths on the defensive and renewed the spirits of the Swabians. Missionaries arriving with the Byzantines converted the Swabians to Catholic Christianity, making them much more appealing to the Romano-Hispanic population, who had always found the Arianism of the Visigoths rather alien. The Romano-Hispanic population rallied to them, but the Swabians overplayed their hand. In 572, proclaiming their intention to "restore" the spiritual authority of the ancient Roman bishoprics, the Swabians invaded Tarraconensis, bringing the Asturias and Cantabria under Swabian "protection".
The Visigoths reacted with a furious counter-invasion. However, the break out of civil war among the Visigoths brought that to a halt. One faction of the revolt was led by Hermengild (a Catholic son of the Visigothic king Leovigild), who erected a short-lived private independent kingdom for himself in Hispalis (Seville). The Basque-Cantabrian mountaineers of the north also revolted against the Visigoths around this time.
Unable to conduct war on so many fronts, the Visigothic king agreed to a truce with the Swabians in 576. The Swabians (once again) escaped annihilation. Alas, this was soon followed by the death of the last powerful Swabian king, Miro, in 583, which prompted at anarchic struggle for succession. The Visigoths used this as an excuse to invade and permanently annex the moribund Swabian kingdom.
Byzantium, in the meantime, had been misgoverning its coastal domain. The emperor's attentions drawn eastwards to Persia from 570s on, the western Mediterranean lands were left to fend for themselves. The Visigothic position in Spain was strengthened in 589 with the new King Recared's conversion to Catholic Christinity and the elevation of Toledo as metropolitan see. The principal Romano-Hispanic objections to Visigothic rule dissipated and several cities (e.g. Corduba) swtiched back to them.
However opportune the moment, the Visigothic hand was stayed. They were still busy becoming Catholic, still licking the wounds of their recent civil war, still busy digesting the Swabians and still trying to impose order on the Basques. The Visigothic king Recared had no desire for an open confrontation with Byzantium at this time.
But the chaos in the east following the coup against Maurice in 602 and the renewal of Byzantine-Persian wars emboldened the Visigoths to make a grab for the Byzantine enclave in Spain. It turned out to be tougher than they imagined. After a painful on-and-off campaign for nearly two decades, the local capital Cartagena (Carthago Spartaria, renamed Justinia by the Byzantines) finally fell (by treachery or negotiation) to the Visigoths in 621.
Iberia was now finally united under Visgothic rule.
The story after that is a bit mundane cloak-and-dagger politics. Royal power declined. Succession was rarely clear and clan rivalries divided the ruling Visigothic class. Into this opening entered the new Catholic Bishops (supported by the Romano-Hispanics), who soon became the kingmakers of the realm. As time progressed, the bishops began asserting themselves more firmly, usurping powers from the secular authorities and centralizing power in Toledo. A confrontation was gradually building up between the landed Visigothic aristocracy on one side and the bishops (& their allies, the Toledo courtiers and the Romano-Hispanics) on the other.
All this came to a head in 572, after the death of King Rencesvint. The Visigothic aristocracy united to impose a king of their own choosing, Wamba, presenting the bishops with a fait accompli. The bishops got their "revenge" in 580, when Wamba fell ill and was presumed dying. In a bizarre comedic twist, the sick Wamba was "tonsured" and ordained into a religious order by the priests at his deathbed -- against his will, said the aristocracy; at his request, replied the bishops. Whatever the case, Wamba recovered only to find out that, as a cleric, he could no longer be king and was thus formally deposed. The new king hurriedly placed by the bishops on the throne, Euric II, tried to reconcile himself with the angry, bewildered Wamba & his clan, but to no avail. Fissures in the Visigothic body politic were deepened.
Euric II died in 587 and was succeeded by his son-in-law, Egica. At first expected to be a conciliatory figure, Egica turns out to be desperately paranoid of both the nobles & the clerics and rules like a freaked-out despot, crushing everybody, esp. nobles & Jews, with an iron fist. The mentally-unstable Egica was eventually replaced by his son Witiza in 700.
Witiza set about on reversing his mad father's policies and mending ties with the aristocracy. But the Visigothic nobles are still smarting and disinclined towards that ill-begotten clan. This time, they manage to find quite some support among the Hispano-Romans, who had also felt the brunt of Egica's crazy fury.
All this explodes into civil war in 710 after the death of Witiza. His son and putative co-ruler ascended as King Akhila II of the Visigoths. But Visigothic nobles, annoyed at the concentration of power in this pungent family, refuse to recognize him and acclaim Duke Roderick of Baetica (unconnected with royal family) as King of the Visigoths. Akhila II and his brothers, Alamundo and Artabas, were defeated in battle by Roderick's supporters.
Now, by this time, the Arabs had defeated & annexed the North African Berbers, taken Tangiers and reached the outskirts of Ceuta. A strange incident involving the ruler of Ceuta, Julian (a Byzantine Patrician? a Visigothic Count? Nobody is quite sure) put things into motion. The story goes that Julian of Ceuta had dispatched his daughter to the Toledo court, but she was allegedly raped by King Roderick himself soon after he took power. Seeking vengeance, Julian aligned himself with the Witizan clan and appealed to the Berbers and Arabs for justice, promising them Ceuta in trust. With Julian's support, the Berber chieftan Tarif ibn Malluq crossed the straits to Tarifa and raided the Spanish coast with ease.
In April, 711, emboldened by the tales of Tarif's success and with the help of Julian of Ceuta, the Berber governor of Tangiers, Tariq ibn Ziyad, landed a 10,000-strong army (7,000 Berber infantry, 3,000 Arab cavalry) in Gibraltar (Jebel al-Tariq, "Tariq's rock"), ostensibly to intervene in the Visigothic civil war on behalf of the Witizan clan and procure justice for his new ally, Julian of Ceuta. He immediately proceeded to take Algeciras and the surrounding countryside. Reinforcements from Tangiers -- some 5,000 Berber infantry -- were landed there.
King Roderick himself, then campaigning in the northeast against a new Basque uprising, heard about the landing and rushed south with his 30,000-strong army. The two armies finally met in July at the Battle of Guadalete (Jerez-de-la Frontera (near Cadiz), possibly further east, near Medina-Sidonia). The Visigoths were crushed. Chroniclers blame the lackluster and even treasonous performance of Visigothic flanks led by counts Sisbert and Oppa (relatives of former king Egica), for the defeat. The Arab cavalry & Berber infantry (now mounted on captured horses) set swiftly about the chase. The remnants of the Roderick's royal army -- including Roderick himself -- were destroyed in the follow-up Battle of Ecija a few days later.
Accompanied by Julian of Ceuta, Tariq took the bulk of his army north towards Toledo, ostensibly to confer with a council of Visigothic nobles of the Witizan party. At news of the approach, Archbishop Sindered of Toledo left hastily for Rome, prompting the evacuation of the population of Toledo, leaving only the Jews who happily opened the doors of the city to Tariq. Cordoba, Malaga and Granada were taken by detachments.
Tariq set up his winter quarters at empty Toledo. Sensing the vacuity of Visigothic power, Tariq decided against supporting the Witizan candidate Akhila II (then busy overrunning Galicia) and instead decided to launch a full-scale Muslim invasion of Spain. News reached Musa ibn Nusayr, the Arab governor of Ifriqiya, who joined Tariq the very next year with a fresh Arab army, some 18,000 strong.
The process of conquest followed, as Tariq, Musa and Abd al-Aziz (Musa's son) proceed in a coordinated campaign to subjugate the peninsula, city by city. The remnant of the Visigothic king's army was defeated Battle of Segoyuela in 713, near Zaragoza. Some areas were taken by contract -- e.g. Murcia, where the local Visigothic ruler Theodimir struck a deal to maintain his independence, helping the Moors take Valencia. Others, such as the Visigothic Count Casio of the Ebro Valley, retained their fiefs by converting to Islam on the spot (Casio was the stem of the famous Banu Qasi clan). The Witizan brothers would not gain the throne they craved, but were granted Galicia as an independent fief under only nominal Muslim suzerainity and were allowed to retain their extensive domains in Andalusia.
Visigothic nobles who did not play ball with the conquerors fled to the inhospitable reaches of the Cantabrian mountains, where they hid among the Basque-Cantabrian mountaineers they had been recently fighting against. It is from here that the Asturian kingdom will stem and the reconquista begin.
I am not sure what happened to Julian of Ceuta. He sort of just disappears from the story after the conquest of Carmona.
As far as Roderick's clan is concerned, there is a bizarre footnote. Strangely, Damascus didn't look kindly on this enterprise and both Tariq and Musa were recalled and demoted in 715. Musa's son, Abd al-Aziz, was temporarily left in charge in Spain, coordinating the conquest from his headquarters in Seville. But sensing his time would also come, Abd al-Aziz took the step of marrying Roderick’s widow Sara (a granddaughter of Witiza, incidentally) and take up the pretensions of a Visigothic king. It is likely Abd al-Aziz had found support among the Visigothic nobility for such a move. But his fellow Arabs would have none of that and had him arrested and executed.
After some more conquering activity by freelance Arab & Berber generals, Damascus finally got around to sending an envoy, al-Samh ibn Malik al-Khawlani, in 718 to organize the incorporation of Spain as a province of the Caliphate.
