Near Eastern Neolithic farmers introduced several species of domestic plants and animals as they dispersed into Europe. Dogs were the only domestic species present in both Europe and the Near East prior to the Neolithic. Here, we assessed whether early Near Eastern dogs possessed a unique mitochondrial lineage that differentiated them from Mesolithic European populations. We then analysed mitochondrial DNA sequences from 99 ancient European and Near Eastern dogs spanning the Upper Palaeolithic to the Bronze Age to assess if incoming farmers brought Near Eastern dogs with them, or instead primarily adopted indigenous European dogs after they arrived. Our results show that European pre-Neolithic dogs all possessed the mitochondrial haplogroup C, and that the Neolithic and Post-Neolithic dogs associated with farmers from Southeastern Europe mainly possessed haplogroup D. Thus, the appearance of haplogroup D most probably resulted from the dissemination of dogs from the Near East into Europe. In Western and Northern Europe, the turnover is incomplete and haplogroup C persists well into the Chalcolithic at least. These results suggest that dogs were an integral component of the Neolithic farming package and a mitochondrial lineage associated with the Near East was introduced into Europe alongside pigs, cows, sheep and goats. It got diluted into the native dog population when reaching the Western and Northern margins of Europe.