Recent studies have suggested that dogs were domesticated during the Last Glacial Maximum (LGM) in Siberia, which contrasts with previous proposed domestication centers (e.g. Europe, the Middle East, and East Asia). Ancient DNA provides a powerful resource for the study of mammalian evolution and has been widely used to understand the genetic history of domestic animals. To understand the maternal genetic history of East Asian dogs, we have made a complete mitogenome dataset of 120 East Asian canids from 38 archaeological sites, including 102 newly sequenced from 12.9 to 1 ka BP (1,000 years before present). The majority (112/119, 94.12%) belonged to haplogroup A, and half of these (55/112, 49.11%) belonged to sub-haplogroup A1b. Most existing mitochondrial haplogroups were present in ancient East Asian dogs. However, mitochondrial lineages in ancient northern dogs (northeastern Eurasia and northern East Asia) were deeper and older than those in southern East Asian dogs. Results suggests that East Asian dogs originated from northeastern Eurasian populations after the LGM, dispersing in two possible directions after domestication. Western Eurasian (Europe and the Middle East) dog maternal ancestries genetically influenced East Asian dogs from approximately 4 ka BP, dramatically increasing after 3 ka BP, and afterwards largely replaced most primary maternal lineages in northern East Asia. Additionally, at least three major mitogenome sub-haplogroups of haplogroup A (A1a, A1b, and A3) reveal at least two major dispersal waves onto the Qinghai-Tibet Plateau in ancient times, indicating eastern (A1b and A3) and western (A1a) Eurasian origins.