Dogs originated more than 14,000 BP, but the location(s) where they first arose is uncertain. The earliest archeological evidence of ancient dogs was discovered in Europe and the Middle East, some 5-7 millennia before that from Southeast Asia. However, mitochondrial DNA analyses suggest that most modern dogs derive from Southeast Asia, which has fueled the controversial hypothesis that dog domestication originated in this region despite the lack of supporting archeological evidence. We propose and investigate with Y chromosomes an alternative hypothesis for the proximate origins of dogs from Southeast Asia--a massive Neolithic expansion of dogs from this region that largely replaced more primitive dogs to the west and north. Previous attempts to test matrilineal findings with independent patrilineal markers have lacked the necessary genealogical resolution and mutation rate estimates. Here, we used Y chromosome genotypes, composed of 29 single-nucleotide polymorphism (SNPs) and 5 single tandem repeats (STRs), from 338 Australian dingoes, New Guinea singing dogs, and village dogs from Island Southeast Asia, along with modern European breed dogs, to estimate the evolutionary mutation rates of Y chromosome STRs based on calibration to the independently known age of the dingo population. Dingoes exhibited a unique haplogroup characterized by a single distinguishing SNP mutation and 14 STR haplotypes. The age of the European haplogroup was estimated to be only 1.7 times older than that of the dingo population, suggesting an origin during the Neolithic rather than the Paleolithic (as predicted by the Southeast Asian origins hypothesis). We hypothesize that isolation of Neolithic dogs from wolves in Southeast Asia was a key step accelerating their phenotypic transformation, enhancing their value in trade and as cargo, and enabling them to rapidly expand and replace more primitive dogs to the West. Our findings also suggest that dingoes could have arrived in Australia directly from Taiwan, independently of later dispersals of dogs through Thailand to Island Southeast Asia.