A migration from Central Europe transformed the genetic make-up of people in Spain during the Bronze Age, a study reveals.
DNA evidence shows the migrants streamed over the Pyrenees, replacing existing male lineages across the region within a space of 400 years.
It remains unclear whether violence played a role or whether a male-centric social structure was more important.
The result comes from the most extensive study of its kind.
Researchers reconstructed the population history of Iberia (modern Spain, Portugal, Gibraltar and Andorra) over 8,000 years - the biggest slice of time tackled by a single ancient DNA study. The region has been a crossroads for different cultures over time.
Their study is published in Science journal.
They extracted and analysed DNA from 403 Iberians who lived between 6,000 BC and AD 1,600.
The Bronze Age migrants traced some of their ancestry to Neolithic (Stone Age) farmers found throughout Europe - including Spain - while the rest of their genetic make-up was like that of people living at the time on the Russian steppe.
This steppe ancestry was introduced to Europe by nomadic herders who migrated west from Asia and the eastern fringes of Europe.
Stone Age crisis
One of the triggers may have been a crisis that caused population numbers to plunge in Europe towards the end of the Neolithic period (which preceded the Bronze Age). Recent studies suggest plague might have played a role.
As the steppe people moved west, they picked up elements of culture from people they mixed with along the way. In Central Europe, one such mixed culture known as the Bell Beaker tradition formed. The Beakers and their descendants may have established highly stratified (unequal) societies in Europe, including Iberia - where they start turning up from 2,500BC.
The researchers looked at the Y chromosome - a package of DNA passed down more or less unchanged from father to son. It can be used to track male-line inheritance. By about 2,000BC, local Y chromosome lineages had been eliminated from the Iberian gene pool, in favour of those carried by the newcomers.
When the team analysed DNA from across the genome - the full complement of genetic material found in the nuclei of cells - they found that later Iberians traced 40% of their ancestry to the new population.
The newcomers - of Bell Beaker origin - brought innovations such as bronze-working (including the manufacture of bronze weapons) and were probably riding horses. These may have given them a military advantage over Stone Age farming societies, but also probably conferred higher social status on males carrying these traditions.
Patterns of inheritance
Co-author Iñigo Olalde, from Harvard Medical School, US, said: "It would be a mistake to jump to the conclusion that Iberian men were killed or forcibly displaced." He added: "The archaeological record gives no clear evidence of a burst of violence in this period."
Instead, the high social status of male newcomers may have been linked to greater reproductive success. "Their male descendants would have inherited the wealth and social status, and themselves also had much higher reproductive success," Dr Olalde told BBC News.
A system that emphasised male power and inheritance could have been key: "A patrilineal and possibly patriarchal social structure would further amplify the observed patterns, as possibly only the first-born son would inherit the clan's properties, whereas the other sons would move out and try to established their own clans, further spreading their Y lineages over new territories," he said.
An even more extreme pattern of replacement occurred at much the same time in Britain, where Beakers replaced 90% of the overall ancestry that was there before they arrived.
"At least in the east and the south-east, we see a change in the settlement patterns... which lasts until the arrival of the Romans," said co-author Dr Carles Lalueza-Fox, from the University of Barcelona.
In this region, the Iron Age Iberian culture established fortified settlements on high ground.
"The Iberians lived in hill settlements and were a violent society, structured along tribal lines. Something clearly changes the social structure that existed in the late Neolithic."
Looking at human remains from an earlier period, the study found that Stone Age hunter-gatherers who traced a significant percentage of their ancestry to some of Europe's earliest settlers, survived in southern Spain until the spread of farming 6,000 years ago.
The team also studied genome data from Moorish Spain (AD 711-1492), when parts of the peninsula were under the control of Muslim emirs of North African origin.
North African influence was present in Iberia from at least the Bronze Age. But the researchers found a dramatic shift in the genetic make-up of people from Moorish-controlled regions after the medieval "Reconquista", when Christian armies seized back control of the peninsula. The conquerors expelled many Muslims, although some were allowed to stay if they converted to Christianity.
While many Moorish individuals analysed in the study seem to have been a 50:50 mix of North African and Iberian ancestry, North African ancestry in the peninsula today averages just 5%.
Modern Iberians derive about 50% of their ancestry from Neolithic farmers, 25% from ancient hunter-gatherers, and 20% from the steppe people.
Faces from Iberia's past
People from the Iron Age Iberian civilization of Spain's east coast generally cremated their dead. The cremation process prevented scientists from extracting DNA from these remains. While the culture was responsible for great works of art, such as the Dama de Elche sculpture, the Iberians also had a violent side. They hammered large nails through the severed heads of enemies killed in combat and exhibited them in public spaces as war trophies. Some 40 such heads were found in the Iberian settlement of Ullastret, allowing scientists to analyse DNA from them.
Two burials in the study were revealed to have high levels of black African ancestry. Both of the individuals were from Granada in southwest Spain, where the last Muslim emirate held out until it was conquered by Christians in 1492. One of the people came from a 10th Century cemetery where bodies were buried in the Islamic tradition - oriented in the direction of Mecca. The other individual is from the 16th Century, after the Christian conquest of Granada. This woman is thought to be from the Morisco community - former Muslims who converted to Christianity (only to be expelled from Spain later on).
After the fall of the Roman Empire, wandering tribes from northern and eastern Europe streamed into Iberia. The Visigoths, who spoke a language related to Swedish, German and English, assumed control of the region. They founded the Spanish monarchy that continues today and introduced laws that formed the basis of those used by later Christian kingdoms. Burials from Pla de l'Horta in northeastern Spain include a mother and daughter of Visigothic origin. Their genomes suggest they had recent ancestry from Eastern Europe, while DNA from the cell's batteries, or mitochondria - which is passed more or less unchanged from mother to children - is of a type associated with East Asian populations. It's a sign of the genetic complexity of the Eastern steppe region where their roots lay.
Follow Paul on Twitter.