Dogs are known to be the oldest animals domesticated by humans. Although many studies have examined wolf domestication, the geographic and temporal origin of this process is still being debated. To address this issue, our study sheds new light on the early stages of wolf domestication during the Magdalenian period (16–14 ka cal BP) in the Hegau Jura region (Southwestern Germany and Switzerland). By combining morphology, genetics, and isotopes, our multidisciplinary approach helps to evaluate alternate processes driving the early phases of domestication. The isotope analysis uncovered a restricted, low δ15N protein diet for all analyzed Gnirshöhle specimens, while morphological examinations and phylogenetic relationships did not unequivocally assign them to one or the other canid lineage. Intriguingly, the newly generated mitochondrial canid genomes span the entire genetic diversity of modern dogs and wolves. Such high mitochondrial diversity could imply that Magdalenian people tamed and reared animals originating from different wolf lineages. We discuss our results in light of three ecological hypotheses and conclude that both domestication and the existence of a specialized wolf ecomorph are highly probable. However, due to their proximity to humans and a restricted diet, we propose domestication as the most likely scenario explaining the patterns observed herein.