33,000-year old dog from the Altai

From the paper:

In conclusion, our analyses support the hypothesis that the Altai specimen is more closely related to domestic dogs than to extant wolves, but we stress the point that these analyses were limited to a single, maternally inherited locus and more sequence data would be needed to obtain a statistically well supported phylogeny and unambiguously resolve the genetic relationship of the Altai specimen. However, this preliminary analysis affirms the conclusion that the Altai specimen is likely an ancient dog with a shallow divergence from ancient wolves. These results suggest a more ancient history of the dog outside the Middle East or East Asia, previously suggested as centres of dog origin. Additional discoveries of ancient dog-like remains are essential for further narrowing the time and region of origin for the domestic dog [5].

An ancient dog with shallow divergence from ancient wolves is probably what we might expect if dogs had been domesticated by some of the first Upper Paleolithic Eurasians a few thousand years prior to the date of this particular specimen.
PLoS ONE 8(3): e57754. doi:10.1371/journal.pone.0057754
Ancient DNA Analysis Affirms the Canid from Altai as a Primitive Dog
Anna S. Druzhkova et al.
The origin of domestic dogs remains controversial, with genetic data indicating a separation between modern dogs and wolves in the Late Pleistocene. However, only a few dog-like fossils are found prior to the Last Glacial Maximum, and it is widely accepted that the dog domestication predates the beginning of agriculture about 10,000 years ago. In order to evaluate the genetic relationship of one of the oldest dogs, we have isolated ancient DNA from the recently described putative 33,000-year old Pleistocene dog from Altai and analysed 413 nucleotides of the mitochondrial control region. Our analyses reveal that the unique haplotype of the Altai dog is more closely related to modern dogs and prehistoric New World canids than it is to contemporary wolves. Further genetic analyses of ancient canids may reveal a more exact date and centre of domestication.
Link