Thousands of years before Hello Kitty and Grumpy Cat, some wild little felines and early farmers made a tacit deal: One side would act a bit docile and kill grain-raiding vermin, and the other would tolerate the cats’ presence and let them eat scraps. That much has long been assumed about cat domestication.

But a new study of DNA from the bones and teeth of more than 200 ancient cats reveals far more about when and how wild cats – solitary, reclusive and very ill-tempered – began to pad their way from the edges of civilisation into our homes and hearts.

An international team of researchers found that cats’ dispersal happened in two waves, first from the Fertile Crescent and later from Egypt. And their migration likely included voyages on Viking ships.

Whether house cats are truly domesticated is a subject of debate among scientists. Their genes aren’t very different from those of wild cats, nor are their bodies or features – they don’t, for example, have the floppy ears and curly tails common to many domesticated animals.

What’s more, though some of them are perfectly happy to curl up on human laps, cats, unlike their canine housemates, are quite capable of living outdoors and feeding themselves.

But at some point, wild felines did come indoors and launched, as the authors call it, “the cat’s worldwide conquest.”

As has been established by previous research, modern-day cats all trace their roots to one subspecies of wild cat, Felis silvestris lybica, that is native to northern Africa and southwest Asia and has proved to be more easily tamed than the four other subspecies.

“To get the real picture, we have to go back to the ancient remains and analyse those,” author Eva-Maria Geigl, an evolutionary geneticist at the Institut Jacques Monod in Paris, said in an interview.

“We tried to get a picture of how the distribution of wild cats occurred before taming occurred.”

The team analysed mitochondrial DNA, which is passed through the mother and better preserved, from remains spanning 9,000 years and locations across Europe, Africa and the Middle East.

One lineage was rooted in the Fertile Crescent, where humans who were still figuring out agriculture more than 10,000 years ago probably realised that some local wild cats were friendly and useful, Geigl said.

“Both sides profited from each other,” she said. “Humans were happy there were less rodents, and the cats had food.”

Not long after the early farmers migrated into Europe about 7,000 years ago, cats began showing up in sites further west, too, suggesting they followed – and were allowed to.

But the study found that it was an Egyptian lineage of cats that really took over parts of Africa and Europe several thousand years later, starting as early as 1700 BC but really accelerating from the 5th to 13th centuries.

Cat remains carrying this lineage were found at a Viking trading port on the Baltic Sea in Northern Germany, lending credence to the idea that cats were providing pest control-services on ships by the Middle Ages.

“When we look at the pattern that we have, this tells us the story of human mobility – war paths, trading paths, and mostly seafaring paths,” Geigl said. “This must have been a cat that was at the time very attractive to people, because it spread very efficiently.”

The researchers, whose paper was published in Nature Ecology & Evolution, also decided to take a closer look at one obvious way today’s Internet stars differ from their wild cousins: their coats. While wild cats have striped, ‘mackerel’, tabby patterns, only domestic tabbies have blotchy fur coats.

That pattern was already known to be caused by one gene mutation, so Geigl and her colleagues looked for it in the ancient feline DNA.

It first showed up in the Middle Ages, suggesting that domestication as we know it – with some sort of selective breeding – did not start until then. This fairly late date provides yet more evidence that the taming of the cat was by no means a quick process.

True selective breeding of cats, the kind that has led to Scottish folds and Bengals, did not begin until the 19th century. Geigl said she’d like to do additional work to determine how black cats, which Egyptian iconography depicted, came about.

But her interest is less about kitties – “It’s a bit of a mystery for me why people are so fond of cats,” she said – and more about the evolutionary stories domestication can tell.

“Evolution occurs faster when you select certain traits,” she said. “In analysing this kind of selection process, you have a model of how evolution works.”