Updated on March 9 at 18:35 p.m. ET

Neanderthal dental plaque is a precious commodity, so it’s a little embarrassing when you’re trying to dislodge a piece and it goes flying across the room. “We just stood still, and everyone’s like: Where is it? Where is it?” recalls Laura Weyrich from the University of Adelaide. “Usually, we try to wrap the skull in foil and work underneath it, but that time, the foil didn’t happen to cover a small area.”

Weyrich and her team of unorthodox dentists eventually found the wayward plaque, and recovered similar samples from the skulls of five Neanderthals. Each was once a colony of microbes, growing on a tooth. But over tens of thousands of years, they had hardened into small, brittle pieces of rock. Still, each nugget contained DNA—from the microbes, and also from whatever the Neanderthals had eaten.

By harvesting and sequencing that DNA, Weyrich has shown that there was no such thing as a typical Neanderthal diet. One individual from Spy cave in Belgium mostly ate meat like woolly rhinoceros and wild sheep, as well as some edible mushrooms. But two individuals who lived in El Sidrón cave in Spain seemed to be entirely vegetarian. The team couldn’t find any traces of meat in their diet, which consisted of mushrooms, pine nuts, tree bark, and moss. The Belgian Neanderthals hunted; the Spanish ones foraged.

“When people talk about the Paleo diet, that’s not paleo, that’s just non-carb,” Weyrich says. “The true paleo diet is eating whatever’s out there in the environment.”

One of the El Sidron Neanderthals even seemed to be self-medicating with edible plants. One of his teeth had an abscess, and his plaque contained a parasite that causes diarrhea. But the plaque also contained Penicillium, the mould that produces the antibiotic penicillin, and poplar bark, a natural source of the aspirin-like painkiller, salicylic acid. The Neanderthal’s medical history—both diseases and treatments—were written in his plaque.

Neanderthals were our closest relatives, who lived in Europe before they went extinct 40,000 years ago. They left their DNA behind in people of Eurasian descent, and their bones in various European caves. By analyzing the chemical content of those bones, some scientists concluded that they were apex carnivores, much like polar bears or wolves. But other teams, who looked at the erosion patterns on Neanderthal teeth or plant matter stuck in their plaque, argued that they occasionally ate a lot of plants.

Weyrich’s results matches all of these earlier ones, and portrays Neanderthals as adaptable and versatile. “Those that occupied southern regions with relatively warm climates, consumed different types of foods, including meat and vegetables,” says Luca Fiorenza from Monash University, who was not involved in the study. “But Neanderthals that lived in very harsh conditions, such as northern Europe, were forced to rely on the limited sources available—meat.”

“We need to revamp the view of Neanderthals as these meat-eating, club-toting cavemen,” adds Weyrich. “They had a very good understanding of what foods were available to them.”

“It’s nice that the different types of data appear to match,” says Anne Stone from Arizona State University. And that’s important because “I don’t think we really understand how dietary DNA is incorporated into plaque.” Do some types of food get incorporated more than others, or is it random? How much do you need to eat of something before it shows up? “We don’t know if we’re looking at their last meal or random food debris from the last ten years,” Weyrich admits.

She didn’t actually set out to study Neanderthal diets. She was more interested in the microbes within the plaque. In an earlier study led by Alan Cooper, she and her colleagues looked at plaque from European hunter-gatherers, who lived between 5,450 and 7,500 years ago, and showed that they carried more diverse range of mouth microbes than people in industrialized societies. That discovery pushed them to look at even older samples. As DNA ages, it degrades and shatters, so the team had to invent new methods to recover microbial DNA from their Neanderthals, and to exclude contaminating modern microbes. Their payoff: the very first microbiomes from extinct hominids.

The mouth microbiomes of the various Neanderthals were as different as their diets. Those form the largely vegetarian individuals from El Sidron were closer to the microbial communities in chimps and Stone Age human gatherers. Those of the Spy Neanderthal clustered with other humans who eat more meat, including European hunter-gatherers and African cattle-farmers. These results suggest that you can use the microbes preserved within fossilized plaque to work out what their long-dead owners may have eaten.

Weyrich’s team also managed to completely sequence one particular microbe called Methanobrevibacter oralis. At 48,000 years old, it’s the oldest microbial genome around. Compared to modern counterparts, which still live in human mouths, it lacks genes for resisting antiseptics and digesting maltose, which suggests that this microbe has adapted to hygiene and changing human diets.

Christina Warriner from the Max Planck Institute for the Science of Human History, who also studies ancient microbiomes, has consistently found that Methanobrevibacter was more common in the human microbiomes of old. “But we know very little about its diversity or function, either today or in the past,” she says. “It is an important reminder of how we're really just scratched the surface of the human microbiome, and how much work there is to do to understand the evolution of this fundamental part of our human biology.”

The microbe might even have something to say about Neanderthal behavior. Weyrich’s team calculated that the Neanderthal strain split apart from those found in modern humans between 112,000 and 143,000 years ago. That’s well after Neanderthals and modern humans themselves split apart, which suggests that the two groups were trading Methanobrevibacter—likely when they had sex, Weyrich speculates. “When you think about swapping oral microbiomes, there are just three ways that’s known to happen—kissing, food sharing, or parental care,” she says. “It suggests that those interactions between modern humans and Neanderthals were more friendly than they have been painted in the past.”

But after the paper was published, and several publications noted Weyrich’s suggestion about kissing in their headlines, Jonathan Eisen from the University of California, Davis, expressed skepticism about the claim. “Maybe the M. oralis comes from food,” he wrote in a blog post. It could have been picked up independently from the environment, or from water contaminated with feces, or from other kinds of sexual contact. A kissing route “it is just one of many and it relies upon a lot of conclusions for which the evidence is tenuous at best,” Eisen said.