Apparently they came from China:
While the descent of dogs from wolves through domestication is non-controversial in genetics, determining the region in the world where this occurred has been more of a question. Earlier studies had suggested a Middle Eastern origin for dogs.
A new study focusing on the lineage of the Y-chromosome indicates that dogs originated somewhere in eastern Asia, south of the Yangtze River.