Swedish researchers say that dogs may have been domesticated much earlier than some other studies suggest.
A genetic study indicates that dogs may have begun to split from wolves 27,000 years ago.
The discovery, in Current Biology, challenges the view that dogs were domesticated much more recently, around 15,000 years ago as humans changed from being hunter-gatherers to farmers.
The study might also explain the deep bond between dogs and humans.
Other researchers had proposed that the domestication of dogs arose with the emergence of agriculture, when human hunter-gatherers settled and formed communities.
The new study, which was led by Dr Love Dalen of the Swedish Museum of Natural History in Stockholm, challenges this view.
"One scenario is that wolves started following humans around and domesticated themselves," he told BBC News.
"Another is that early humans simply caught wolf cubs and kept them as pets and this gradually led to these wild wolves being domesticated. If this model is correct then dogs were domesticated by hunter-gatherers that led a fairly nomadic lifestyle."
Peter Smith, chief executive of the Wildwood Trust in Kent, UK, and a former conservation biologist, says that this might have been the start of the relationship between dogs and humans that has developed and become closer over thousands of years.
"[The study] is showing that the deep, deep connection has existed between man and wolves - now our dogs - for many tens of thousands of years and that is why we love dogs so much. They are part of our own evolution into a modern society," he told BBC News.
The DNA was analysed from a small wolf bone found by Dr Dalen on the Taimyr Peninsula in northern Siberia which was radiocarbon dated to be 35,000 years old.
His lab specialises in being able to piece together the DNA of ancient specimens. Dr Dalen and his team were able to identify the rough genetic code of the animal and to their surprise they discovered that its DNA was half way in between dogs and wolves.
The results suggest that the split between dogs and wolves happened a few thousand years later.
According to Dr Dalen, dogs were either domesticated at that time, or the population split into modern wolves and a wild ancestor of modern dogs that later became extinct.
"We think the simplest explanation is that dogs were domesticated at the time of the split," he says.
An earlier genetic study of several different kinds of modern dogs and wolves had estimated that dogs and wolves diverged between 10,000 and 15,000 years ago. Remains of what seem to be dogs also start appearing in the archaeological record around 15,000 years ago, and so this became the received wisdom.
However, the new study is more accurate because it used the actual DNA of an ancient wolf as its baseline.
"That the split between dogs and wolves happened around 30,000 years ago seems fairly definitive," says Dr Dalen.
But some researchers still dispute that this was the moment that the first dogs began to emerge. They believe that domestication was a more complex event.
A group led by Dr Greger Larson at Oxford University is working on a project to study the origin of dogs. Dr Larsen's team is in the process of collecting 4,000 skulls and teeth of different ages from across the world which they plan to analyse genetically and evaluate the way in which their shapes have changed through time.
Dr Larson says that the archaeological evidence is biased towards the later stages of dog evolution because dogs probably didn't start looking like dogs as we know them until relatively recently.
However, he believes the process was a continuous one, so much so that he has banned the use of the words "dog" and "wolf" in his lab.
"It probably started with an unconscious phase where wolves were gradually getting used to human populations, following them around and eating their waste products. The changes that we now ascribe that differentiate dogs and wolves may not have emerged for a very long time," he told BBC News.
Dogs and humans
The great prize in the field is to track the genetic changes that resulted from the ever closer relationship between dogs and humans. But according to Dr Larson, those first changes were in behaviour and are thus difficult to track.
"There were probably small changes in many genes which makes it much more difficult to pin down."
Another interesting finding from the Swedish study is that it also shows that the modern-day dogs most closely related to the ancient Taimyr are the Siberian Husky and Greenland sledge dog, according to Dr Pontus Skoglund of Harvard Medical School, who also worked on the study.
"Our study provides direct evidence that a Siberian Husky you see walking down the street shares ancestry with a wolf that roamed northern Siberia 35,000 years ago."
Follow Pallab on Twitter