Modern humans migrated to Britain around 45,000 years ago, and it had been assumed that paler skin had evolved shortly after.
But a human man that lived in Britain 10,000 years ago during the Mesolithic had dark to black skin, DNA analysis reveals - showing that reduced skin pigmentation arrived in the British Isles much later than we thought.
He's called the Cheddar Man, because his remains were found in 1903 in Gough's Cave in Cheddar Gorge, Somerset.
It was this cool, stable limestone cave environment that preserved the Cheddar Man's DNA for thousands of years - and he is the oldest British individual to have had his whole genome sequenced.
As well as the very dark skin, he also had blue eyes and dark curly hair, according to the DNA analysis conducted by researchers at University College London and the Natural History Museum in London - and, like all Europeans of the time, he was lactose intolerant.
Although Britain has been inhabited by a variety of human species for hundreds of thousands of years, the earliest evidence of modern humans is between 40,000 and 45,000 years old.
"Until recently it was always assumed that humans quickly adapted to have paler skin after entering Europe about 45,000 years ago," Natural History Museum researcher Tom Booth said.
"Pale skin is better at absorbing UV light and helps humans avoid vitamin D deficiency in climates with less sunlight."
Although the Cheddar Man has the genetic markers of skin pigmentation usually found in sub-Saharan Africa, the result is consistent with other Mesolithic human remains found throughout Europe.
"He is just one person, but also indicative of the population of Europe at the time," Booth said.
"They had dark skin and most of them had pale coloured eyes, either blue or green, and dark brown hair."
To obtain DNA from ancient remains, the best place to look are the densest bones available. These are more likely to have protected the DNA inside - leg bones or teeth are often good bets, but it turns out the best place is the inner ear.
The densest bone in the human body is the petrous part of the temporal bones at the sides of the skull, and it was this that the team drilled into to extract a sample. They made a tiny hole just 2 millimetres in diameter.
The team then subjected the extract to shotgun sequencing, which involves defining millions of tiny fragments of the genome and mapping them against the modern human genome.
This allowed the team to compare markers for physical traits, and determine what the Cheddar Man could have looked like.
Once that information had been confirmed, palaeontological reconstruction experts reconstructed his face.
Cheddar Man was about 166 centimetres (5'5″) tall, and died in his 20s. There is damage to his skull that could indicate an accidental or violent death, although it could also have been damaged during excavation.
Unusually, he was buried alone - other burials from the time were usually communal - his body covered with sediment in the cave. But whether he was covered purposefully or the sediment built up over time is, again, unknown.
We know from other archaeological research that he was a hunter-gatherer, and during his life he would have eaten seeds, nuts, red deer, wild aurochs, and freshwater fish.
Around 10 percent of the British population shares DNA with the Mesolithic population to which the Cheddar Man belonged, but they aren't direct descendents.
Instead, experts believe that those Mesolithic Europeans were replaced by a new population of farmers that migrated into Britain at a later time.
A documentary describing the research, First Brit: Secrets of the 10,000 Year Old Man, is due to air on UK's Channel 4 next week.