The tumour originated in a single dog 11,000 years ago but outlived its host by transferring to another dog - and is still on the march today.
An international team led by Cambridge scientists mapped its progress based on DNA from 449 tumours in 39 countries.
Some of the cancer's more recent travel between continents, they found, aligns with maritime trade routes.
But apart from reflecting the shared migration history of dogs and humans, the tumour's genetic history includes a surprising quantity of DNA pilfered from its hosts.
The findings, reported in the open access journal eLife, are based on mitochondrial DNA - small, circular chains of genetic information parcelled up in mitochondria, the "batteries" of cells.
And the study centres on a rare but recurring event: at least five times during the tumour's poisonous coexistence with millions of dogs through the ages, it appears to have traded mitochondrial DNA with its host.
"Normally the dog is a transient host - and then the tumour gets passed on to more dogs. But what has happened occasionally is that DNA from the dog actually enters the tumour cell," explained Dr Elizabeth Murchison, a Wellcome Trust Investigator at the University of Cambridge and the paper's senior author.
"So rather than carrying the mitochondria of the original dog that lived 11,000 years ago, the tumour is now carrying the host dog's mitochondria. And it's going to pass those on to the next dog."
Those five wholesale transfer events create five major ancestral groups or "clades" for the tumours that exist today. By further analysing the gradual, piecemeal mutations that accumulate during the rest of the cancer's history, Dr Murchison and her colleagues built up a family tree and a clear picture of the disease's journey around the planet.
ANNA CZUPRYNA/TRANSMISSIBLE CANCER GROUP CAMBRIDGE
Known as canine transmissible venereal tumour (CTVT), the cancer can affect any breed of dog and is usually found in the animal's genitals. From there it is easily transmitted during sex, and is currently found in dogs on six continents.
It is one of just a handful of infectious cancers known to science, including the face tumour threatening Tasmanian devils with extinction.
Because all CTVT cells can be traced back to a single dog some 11 millennia in the past, it is regarded as the oldest and most prolific cancer lineage in nature.
A previous study showed that the tumour was able to steal DNA from its host dogs.
Dr Murchison, working with a large international team, conducted a thorough search for such genetic thievery.
"Every time the DNA from the host dog has been picked up, that acts as a little genetic flag for us," she told the BBC.
One such event, dated to about 500 years ago, spawned cancerous progeny in a tell-tale, transcontinental pattern.
SCIENCE PHOTO LIBRARY
"We were able to estimate the time since the mitochondrial transfer events, by counting the number of mutations. And one of them really seems to just track around maritime trade routes, in the last few hundred years.
"We found it along the coast of West Africa, in the Cape Verde islands, Brazil, South Africa, India, and some parts of southern Europe.
"You can kind of imagine those dogs on boats, which must have taken that tumour around with them."
For the geneticists involved, the highlight of this large study was a cancerous specimen from Nicaragua which showed something never seen before: not only had the tumour pinched some mitochondrial DNA from its canine host, but the two sequences had been spliced together.
This "recombination" is a routine part of how the regular DNA in our chromosomes gets jostled around - but evidence of it happening in mitochondria is rare and controversial. Many researchers "still don't really believe" it is possible, Dr Murchison said.
And it has never been seen in the mitochondria of a cancer cell.
"Mitochondrial DNA recombination could be happening on a much wider scale, including in human cancers, but it may usually be very difficult to detect," said Máire Ní Leathlobhair, co-first author of the study.
"In human cancer, the tumour's mitochondrial DNA is likely to be very similar to the mitochondrial DNA in the patient's normal cells, so the result of recombination would be almost impossible to recognise."
Follow Jonathan on Twitter