PLoSOne has a study on remains of a domesticated dog in Siberia ca.
33,000 ybp. This appears to be the earliest known such find,
approximately contemporaneous with one found in Europe.
The study suggests multiple instances of domestication, with the oldest
remains being of a different species than later dogs.
Virtually all well-documented remains of early domestic dog (Canis
familiaris) come from the late Glacial and early Holocene periods (ca.
14,000–9000 calendar years ago, cal BP), with few putative dogs found
prior to the Last Glacial Maximum (LGM, ca. 26,500–19,000 cal BP). The
dearth of pre-LGM dog-like canids and incomplete state of their
preservation has until now prevented an understanding of the
morphological features of transitional forms between wild wolves and
domesticated dogs in temporal perspective.
We describe the well-preserved remains of a dog-like canid from the
Razboinichya Cave (Altai Mountains of southern Siberia). Because of the
extraordinary preservation of the material, including skull, mandibles
(both sides) and teeth, it was possible to conduct a complete
morphological description and comparison with representative examples of
pre-LGM wild wolves, modern wolves, prehistoric domesticated dogs, and
early dog-like canids, using morphological criteria to distinguish
between wolves and dogs. It was found that the Razboinichya Cave
individual is most similar to fully domesticated dogs from Greenland
(about 1000 years old), and unlike ancient and modern wolves, and
putative dogs from Eliseevichi I site in central Russia. Direct AMS
radiocarbon dating of the skull and mandible of the Razboinichya canid
conducted in three independent laboratories resulted in highly
compatible ages, with average value of ca. 33,000 cal BP.
The Razboinichya Cave specimen appears to be an incipient dog that did
not give rise to late Glacial – early Holocene lineages and probably
represents wolf domestication disrupted by the climatic and cultural
changes associated with the LGM. The two earliest incipient dogs from
Western Europe (Goyet, Belguim) and Siberia (Razboinichya), separated by
thousands of kilometers, show that dog domestication was multiregional,
and thus had no single place of origin (as some DNA data have suggested)
and subsequent spread."