They wandered in from Siberia a few thousand years after humans first undertook the same perilous journey onto the North American continent, looking for a new home.
For millennia the two species shared the land. Perhaps even hunted together. And then, for some reason, the first non-wolf dogs to set foot in the New World disappeared, leaving not just a mystery to solve but something far more sinister.
A comprehensive study on the DNA of ancient dog remains found on the American continent has uncovered a population of canines distinct from the wolves and coyotes that already lived there. But it existed for a period spanning just 9,000 years.
In a rather unsettling twist, it was also discovered that these dogs left something of a legacy – in the form of a rather unusual disease.
Researchers from around the globe collaborated to compare sequences of mitochondrial DNA from 71 ancient specimens of North American and Siberian dogs, as well as nuclear DNA from a further 7 sets of remains.
The oldest bones extracted from a grave in western Illinois had already been radio carbon dated to just under 10,000 years old, thousands of years after the first signs of human inhabitation on the North American continent.
Comparing the sequences with 145 mitochondrial genomes from other canid species resulted in a family tree with the so-called 'precontact dogs' on a branch of their own, closely related to another ancient group from Zhokhov Island in Eastern Siberia.
The find suggests the first dogs in America weren't companions of the first small communities to journey out of Siberia, but instead were either imported much later, or had reason to take up the arduous migration into new territory on their own.
"This study demonstrates that the history of humans is mirrored in our domestic animals," says the study's senior author Greger Larson from Oxford University.
"People in Europe and the Americas were genetically distinct, and so were their dogs."
From their origins in Siberia, the dogs spread down through the continent with human settlements, becoming partially or even completely domesticated as the years ticked by.
It's likely they looked somewhat similar to the wolves that preceded them by a few thousand years, also journeying across the land bridge formed by the Ice Age's lowered sea level.
The 19th century American naturalist John James Audubon remarked, "The Indian dogs which I saw here so very closely resemble wild wolves, that I feel assured that if I was to meet with one of them in the woods, I should most assuredly kill it as such."
While it's yet to be confirmed, there are some signs that the wolves and coyotes inherited a few of the pre-contact dog genes.
Today these wolf-like dogs are no more. Their disappearance coincided with colonisation, their ultimate fate left to speculation.
"This suggests something catastrophic must have happened, and it's likely associated with European colonisation," says Laurent Frantz from the University of Oxford.
"But we just do not have the evidence to explain this sudden disappearance yet."
Introduced diseases is one possibility. If that was the case, these first dogs might have left a rather disturbing legacy.
Canine transmissible venereal tumours (CTVT) are a rare form of cancer that can be transmitted between hosts, not unlike the deadly devil facial tumour disease (DFTD) that threatens populations of Tasmanian devils.
As a cancer, the cells contain traces of its progenitor locked away in its own genes.
Using the cancer's sequence, the researchers traced the disease back to a dog more closely related to pre-contact dogs than modern Arctic ones, one that lived no earlier than 8,225 years ago.
"It's quite incredible to think that possibly the only survivor of a lost dog lineage is a tumour that can spread between dogs as an infection," says University of Cambridge veterinarian Maire Ní Leathlobhair.
Further research in genetics and archaeology might help unravel the mystery of this ancient dog's sad fate.
Whatever happened, at least now we know it deserves to have a distinct place in the history books.
This research was published in Science.