Advances in the isolation and sequencing of ancient DNA have begun to reveal the population histories of both people and dogs. Over the last 10,000 y, the genetic signatures of ancient dog remains have been linked with known human dispersals in regions such as the Arctic and the remote Pacific. It is suspected, however, that this relationship has a much deeper antiquity, and that the tandem movement of people and dogs may have begun soon after the domestication of the dog from a gray wolf ancestor in the late Pleistocene. Here, by comparing population genetic results of humans and dogs from Siberia, Beringia, and North America, we show that there is a close correlation in the movement and divergences of their respective lineages. This evidence places constraints on when and where dog domestication took place. Most significantly, it suggests that dogs were domesticated in Siberia by similar to 23,000 y ago, possibly while both people and wolves were isolated during the harsh climate of the Last Glacial Maximum. Dogs then accompanied the first people into the Americas and traveled with them as humans rapidly dispersed into the continent beginning similar to 15,000 y ago.