An ancient dog bone unearthed in a cave in northern Spain has just been dated by scientists to 17,000 years ago. This makes it the oldest dog remains found thus far in Europe, with important implications for the origin story of man’s best friend.

Dogs (Canis lupus familiaris) have been with humans for a very long time. They’re actually the first species that we’ve domesticated, sometime between 15,000 and 20,000 years ago, long before we learned to tame and farm cattle, sheep, chicken or guinea pigs. But despite the strong bond between humans and dogs, there is a surprising number of mysteries surrounding canine domestication.

Contrary to conventional wisdom, dogs are not the direct descendants of the gray wolves (Canis lupus) that persist today in the Northern Hemisphere, but rather descend from an unknown and extinct wolf. When and where exactly dogs were domesticated are other unsolved questions. And no one knows for sure exactly how the two species started their relationship seeing how wolves are highly independent and can be quite aggressive, with the leading hypothesis being that some friendly Ice Age wolves got used to people who gave them scraps or let them raid garbage piles. Over time, these tamer individuals were selected, breeding increasingly less aggressive individuals that moved with hunter-gatherer communities.

Previously, studies of canine DNA have pinpointed the geographical origin of dog domestication to widely different locations, from China to the Middle East. However, the most ancient undisputed dog remains have been found in Eurasia, the oldest being identified in Abri le Morin, France, dating from around 15,000 years ago, associated with the Magdalenian — one of the oldest Upper Paleolithic cultures.

However, in addition to ancient dog remains, paleontologists have also discovered much older remains of dog-like wolves, some as old as 40,000 years. These proto-dogs, which were neither wolves nor dogs, may have represented an intermediate step in canine domestication, although this is contested, with some authors proposing these ancient canids may have been just another ecotype of wolves in the Upper Paleolithic rather than the result of some early domestication attempt.

An ancient cracked humerus bone first unearthed in 1977 in a cave in Eralla, in Spain’s Basque Country, is complicating the story of canine domestication further, partially answering some old questions while inviting new mysteries.

Initially, researchers couldn’t decide whether the bone belonged to a dog or a dhole (an Asian wild dog related to domesticated dogs and foxes). Now, a team of geneticists and anthropologists at the University of the Basque Country in Spain used a combination of radiocarbon dating, and genetic and morphological analysis that confirmed the identification of this specimen as Canis lupus familiaris, the domesticated dog.

The direct dating of the bone using carbon-14 dating and particle accelerator mass spectrometry shows the remains are 17,000-17,500 years old, placing the Erralla dog well within the Magdalenian period and making it perhaps the oldest ancient dog remains ever found in Europe or even elsewhere for that matter.

The careful study of the bone’s shape suggests the Erralla dog is neither wolf nor ‘dog-like’, but rather definitively a domesticated dog not all that different from present-day pooches. Meanwhile, the genetic analysis shows that the Erralla dog shared the same mitochondrial lineage as other Magdalenian dogs found in France or Spain. Based on this mitochondrial information, winding back the molecular clock suggests that dogs first appeared some 22,000 years ago, at the very peak of the Last Ice. This means that much older dog remains await to be found.

During the Last Glacial Maximum, or what we commonly refer to as the Last Ice, much of Eurasia was covered by ice sheets and ice caps covered the Alps and the Pyrennes. But as this never-ending winter unfolded over much of northern Europe, the Iberian Peninsula with its warmer climate, though manageably frigid, acted as a refuge for numerous species of birds and animals that went extinct elsewhere, as well as the hunter-gatherers like the Magdalenian culture. And this also included their new companions: Ice Age doggos.

“In conclusion, the data analyzed to date indicate that, during the Magdalenian, the domestic dog was part of the groups of Western European hunter-gatherers. The dog from Erralla (17,410–17,096 cal. BP) is one of the oldest specimens identified as Canis lupus familiaris, and it shares the mitochondrial haplogroup C with the Magdalenian dogs analyzed to date. These findings prove that this haplogroup existed in Europe at least since the Lower Magdalenian, during the Early Dryas, and lead us to consider a possible domestication of the wolf older than what has been proposed so far, at least in Western Europe,” the researchers conclude in the Journal of Archaeological Science: Reports.