The study, which was recently published in Science, sheds entirely new light on who we are as Europeans.
"From a genetic point of view he's an European," says Professor Eske Willerslev, Director of the Centre for GeoGenetics at the University of Copenhagen, who was involved in the new study, and adds: “Actually, he is closer to Danes, Swedes, Finns and Russians than to Frenchmen, Spaniards and Germans”.
The new results reveal that the man is the oldest that we know of so far to genetically represent a separate line from the forebears of present-day Asians.
This is decisive when it comes to dating one of the most important events in history.
"We can now date the separation time between Asians and Europeans," says Professor Rasmus Nielsen from the University of Copenhagen and the University of California, Berkeley, who was also involved in the study.
He points out that the Kostenki genome sets a line 37,000 years ago. Here the lines must have split, while the 45,000-year-old genome from the recently discovered Ust' Ishim in Siberia sets the limit in the other direction.
This gives the answer to one of the biggest questions in the history of mankind; scientists now know that it is within the 8000 year gap that Europeans and Asians went their separate ways.
Previously the impression was that our forebears lived in separate populations and had children within the group, instead, Willerslev now paints a very different picture consisting of one large meta-population.
A meta-population consists of several populations which mate with each other.
The meta-population is connected through the neighbour's neighbours, consisting of people who generally resemble each other a lot, but who also have their own unique traits.
"It was a huge, complex network, and not separate branches that lived in isolation,” says Willerslev.
He believes the Europeans must have been one enormous meta-population stretching across Europe, the Middle East and Central Asia.
It is possible to follow the genetic trail; all the way from the Kostenki genome, to hunter-gatherers in Siberia 25,000 years ago and farmers 7-8000 years ago in Spain, Luxembourg and Sweden, up to present-day Europeans.
A study published in September, led by two professors, Johannes Krause from Eberhard Karl's Universität Tübingen in Germany and David Reich from Harvard University in the US, concluded that present-day Europeans descends from at least three separate groups.
David Reich acknowledges the importance of the new study, but is not convinced that it changes history very much.
"It's wonderful to have the Kostenki genome and it’s also important and interesting to find a degree of continuity from the population represented by Kostenki to present-day Europeans," says Reich and adds:
"On the basis of a statistical test or two, it's a pretty far-reaching conclusion as to how our history proceeded. However, It’s exciting - if it's true”.
Although Willerslev and Nielsen admit that further tests could be carried out, they are pretty convinced that their idea is waterproof.
The Swedish scientist Pontus Skoglund from Harvard University, who was not involved in either Willerslev's new study or that of Reich, published in September, also finds it quite convincing.
"It'll be interesting to see more tests done, and as a field we need the time to digest these conclusions. But for now, it looks as though it may well be true, in which case it is an extremely important result," says Skoglund.
It turns out that Scandinavians are more closely related to the Kostenki man than any other now-living population. This means that Scandinavians are the earliest Europeans.
However, the genome also indicates that many European traits, including those from the Middle East, were already present in the first Europeans.
So from a genetic point of view it makes no sense to categorise the Scandinavians as a separate people. "In those days people didn't respect our virtuous, well-ordered ideas of belonging to specific groups," comments Professor of Evolutionary Studies, Peter C. Kjærgaard, from Aarhus University.