Thousands of years before cats took up residence in 37 percent of American households, and managed to outnumber dogs by roughly 75 million across the globe, they were hopping continents with farmers, ancient mariners, and even Vikings, scientists have found.
In the first large-scale study of ancient feline DNA, the results reveal how our inscrutable friends were domesticated in the Near East and Egypt some 15,000 years ago, before spreading across the globe and into our hearts.
The study was presented at the International Symposium on Biomolecular Archaeology in Oxford, UK back in 2016, and sequenced DNA from 209 cats that lived between 15,000 and 3,700 years ago - so from just before the advent of agriculture right up to the 18th century.
Found in more than 30 archaeological sites in Europe, the Middle East, and Africa, these ancient feline specimens are helping researchers to piece together the beginnings of an animal that we share our beds with, but know surprisingly little about.
"We don't know the history of ancient cats. We do not know their origin, we don't know how their dispersal occurred," one of the team, Eva-Maria Geigl, an evolutionary geneticist from the Institut Jacques Monod in France, told Ewen Callaway at Nature.
Analysing the DNA of cats found in ancient Egyptian tombs, burial sites in Cyprus, and an old Viking settlement in Germany, the team found that cats likely experienced not one, but two, waves of expansion during their early history.
The first wave is a story you're probably familiar with.
When the team looked the mitochondrial DNA - genetic information that's passed on from the mother only - they found that wild cats from the Middle East and the fertile eastern Mediterranean shared a similar mitochondrial lineage.
This suggests that small wild cats spread through early agricultural communities, because they were attracted to the mice that were attracted to the grains. The farmers likely encouraged their presence, because, let's face it, those rodent-killing machines would have been mighty cute company.
Then, thousands of years after this, the research points to a separate mitochondrial connection between cats descended from those in Egypt to ones in Eurasia and Africa.
"A mitochondrial lineage common in Egyptian cat mummies from the end of the 4th century BC to the 4th century AD was also carried by cats in Bulgaria, Turkey and sub-Saharan Africa from around the same time," Callaway reports.
This second wave of expansion has been attributed to ancient sea-faring people - farmers, sailors, and Vikings - because the cats were likely encouraged to stay on board to keep their rodent problem in check.
Geigl cites cat remains with this same maternal DNA connection found at a Viking site in northern Germany, and dated to between the 8th and 11th century AD.
"I didn't even know there were Viking cats," Pontus Skoglund, a population geneticist from Harvard Medical School, who wasn't involved in the study, told Nature.
It's important to note that these are just the team's initial findings, and they could be subject to change as the analysis goes deeper.
But that's an exciting prospect, because while we have the history of dog domestication pretty well mapped out, we're only just beginning to figure out the mystery behind our feline friends. Although, let's be honest, they probably prefer it that way.
A version of this article was originally published in September 2016.