Until 2009, dogs were believed to have been domesticated about 17,000 years ago, long after Neandertals were already extinct.Now some paleontologists are re-thinking that.
None of these ancient dog skulls date exactly to the period of modern human–Neandertal overlap, but the domestication process must have been underway even before the first identifiable dog entered the fossil record. The rapidly developing consensus is that dogs were domesticated during the period when both modern humans and Neandertals [new spelling] lived in Europe. So far, all of these early dogs are from modern-human sites. Several lines of evidence suggest that dogs and wolves were especially revered by those humans.More on ritual burial of dogs and calculations from Finland on dogs' utility in hunting large animals. (Hat tip, Patrick Burns.)