The bacteria that caused the devastating Black Death plague in medieval times may have roots going all the way back to the Stone Age, when ancient humans first carried them into Europe.

Researchers are saying they analyzed the genomes of the bacterium Yersinia pestis, which causes the plague, from samples that lived between 3,700 and 4,800 years ago. They found patterns suggesting it was introduced to the heart of Europe during the Stone Age, according to their study in the journal Current Biology. They say this happened at the same time large numbers of nomads migrated there from the Eurasian steppe, a central strip of land with a temperate environment that stretches across Asia and eastern Europe — thousands of years before the historical outbreaks that read about today in textbooks.

The connection between those events comes from a connection of DNA: The scientists saw signs in the bacteria genomes recovered from the bones of six Europeans that the microorganisms were closely related to each other, despite being separated by large geographical distances. According to the Max Planck Institute for the Science of Human History, the nomads were expanding their territory into central Europe about 4,800 years ago. They carried the plague bacteria throughout the continent with them.

“The plague genomes recovered by the researchers confirm that changes were occurring during this period in genes related to plague virulence, as suggested in prior research,” the institute explained. Although further research will clear up exactly how those changes made the plague more dangerous, “it is possible that Y. pestis was already capable of causing large-scale epidemics before it developed these traits.”

When nomadic people brought Y. pestis into central Europe, it would be roughly another 4,000 years before the most famous outbreak of the plague, the 14th-century Black Death that is almost synonymous the Middle Ages.

Scientists had previously discovered traces of Y. pestis in prehistoric people from Eurasia and southern Siberia, showing that it could have been causing human disease even before the beginning of the plague’s documentation, according to the study. The genome sequencing performed in this new research shows more detail about how the bacteria spread over the millennia.

“By analyzing ancient forms of the disease, the researchers hope to learn more about the evolution of the plague and how it became more virulent over time,” according to the Max Planck Institute.

It is possible that prehistoric people were migrating to avoid the disease or that they were affected by the bacteria differently.

“The threat of Y. pestis infections may have been one of the causes for the increased mobility during the late Neolithic-early Bronze Age period,” lead study author Johannes Krause said in the statement. “It’s possible that certain European populations, or the steppe people, may have had a different level of immunity.”