Dogs were present in the Americas prior to the arrival of European colonists, but the origin and fate of these pre-contact dogs are largely unknown. We sequenced 71 mitochondrial and seven nuclear genomes from ancient North American and Siberian dogs spanning ~9,000 years. Our analysis indicates that American dogs were not domesticated from North American wolves. Instead, American dogs form a monophyletic lineage that likely originated in Siberia and dispersed into the Americas alongside people. After the arrival of Europeans, native American dogs almost completely disappeared, leaving a minimal genetic legacy in modern dog populations. Remarkably, the closest detectable extant lineage to pre-contact American dogs is the canine transmissible venereal tumor, a contagious cancer clone derived from an individual dog that lived up to 8,000 years ago.