In the winter of 406, the Vandals and Suevi and the (Sarmatian) Alans crossed the frozen Rhine en masse. Three years later they crossed the Pyrenees into the Iberian Peninsula and divided the western parts, roughly corresponding to modern Portugal and western Spain as far as Madrid, between them.

In 412 they were followed by the Visigoths, who had been considerably Romanized but had sacked Rome two years earlier. They founded the Visigothic Kingdom of Toulouse (in the south of modern France) and gradually expanded their influence into the Iberian peninsula at the expense of the Vandals and Alans, who moved on into North Africa without leaving much permanent mark on Hispanic culture. The Visigothic kingdom shifted its capital to Toledo and reached a high point during the reign of Leovigild. The Visigoths were Arian Xians, but respected Roman institutions and especially legal codes so there was continuity in forms of government and historical records for most of the period between 415, when Visigothic rule in Spain began, and 711, when it is traditionally said to end. The proximity of the Mediterranean and continuation of some trade there encouraged this. The Arian Visigothic nobility kept apart from the local Catholic population and looked to Constantinople for style and technology; other than a brief incursion of Byzantine power in Córdoba, their main rivals for power were the Catholic bishops, but in 546 the Council of Lerida restricted the clergy and subjected them to the law under the blessings of Rome. Arianism briefly spread, but in 587 King Reccared, having converted to Catholicism, launched a movement to unify the various religious doctrines in Spain. The Visigothic nobility saw little reason to mingle with their subjects; the most noticeable effect of their rule was that the cities became depopulated because they preferred to live in the country.

By 711 Arabs and Berbers had converted to Islam, which by the 8th century dominated all of North Africa. A raiding party led by Tariq ibn-Ziyad was sent to intervene in a civil war in the Visigothic kingdoms in Iberia. Crossing the Strait of Gibraltar, it won a decisive victory in the summer of 711 when the Visigothic king Roderic was defeated and killed on July 19 at the Battle of Guadalete. Tariq's commander, Musa bin Nusair, quickly crossed with substantial reinforcements, and by 718 the Muslims dominated most of the peninsula. Their advance into Europe was stopped by the Franks under Charles Martel at the Battle of Tours in 732. Muslim Spain was called Al-Andalus and was variously subdivided. What is known as the reconquista began in 1085 when Alfonso VI of Castile captured Toledo; by 1236, with the fall of Córdoba, the Kingdom of Granada remained the only Muslim-ruled territory in what is now Spain. The Portuguese reconquista culminated in 1249 with the conquest of Algarve by Afonso III. In 1238, Granada officially became a tributary state to the Kingdom of Castile, then ruled by Ferdinand III, and on January 2, 1492 the reconquest was completed when Muhammad XII of Granada surrendered complete control of Granada to the joint sovereigns (Los Reyes Católicos - "the Catholic Monarchs"), Ferdinand and Isabella.