Writing in Current Biology journal, researchers suggest the deadly bacterium entered Europe with a mass migration of people from further east.
They screened more than 500 ancient skeletal samples and recovered the full genomes of plague bacteria from six individuals.
These six variously date to between Late Neolithic and Bronze Age times.
The plague-positive samples come from Russia, Germany, Lithuania, Estonia and Croatia.
Plague may already have been capable of causing epidemics in the Stone Age
"The two samples from Russia and Croatia are among the oldest plague-positive samples published. They are contemporary with [a] previously published sample from the Altai region [in Siberia]," co-author Alexander Herbig from the Max Planck Institute for the Science of Human History in Jena, Germany, told BBC News.
The plague bacterium, Yersinia pestis , was responsible for several major historic pandemics, including the infamous Black Death in the 14th Century, which is estimated to have killed between 30% and 60% of Europe's population.
Analysis of the ancient plague DNA shows that Y. pestis genomes from the Neolithic and Bronze Age were all fairly closely related.
This is intriguing because the individuals from which they were recovered come from such a wide geographic area.
"This suggests that the plague either entered Europe multiple times during this period from the same reservoir, or entered once in the Stone Age and remained there," said co-author Aida Andrades Valtueña, also from the Max Planck Institute in Jena.
In order to clarify which scenario was most likely, the researchers looked for clues from archaeology and from the analysis of ancient human DNA.
From about 4,800 years ago, there was a major expansion of people into Europe from a region called the Caspian-Pontic Steppe in present-day Russia and Ukraine.
Yersinia pestis is the bacterial agent of plague
These people carried a distinctive genetic component - also seen in Siberians and Native Americans - that had not been present in Europeans before the late Neolithic.
The earliest indications of plague in Europe coincide with the arrival of this "steppe ancestry" in Europeans.
Dr Herbig said this supports "the view that Y. pestis was possibly introduced to Europe from the steppe around 4,800 years ago, where it established a local reservoir before moving back towards Central Eurasia".
Analysis shows that plague bacteria genes related to virulence were changing at this time. But further work is needed to determine how these changes affected the severity of the disease.
However, it's certainly possible that these early Y. pestis bacteria were already capable of causing large-scale epidemics.
The steppe people could have been moving to get away from a plague outbreak - although the effects of climate change on the landscape in this region may also have played a role.
The disease could also have been involved in profound genetic changes seen in European populations at this time. In some regions, the steppe people appear to have largely replaced the previous Neolithic inhabitants.
"It's possible that certain European populations, or the steppe people, may have had a different level of immunity [to Y. pestis ]," said Johannes Krause, from the Max Planck Institute.
Dr Herbig commented: "The plague might have been a factor among others that promoted the migration processes during this time period. However, our current data has insufficient resolution to see how specific regions within Europe were affected differently by the disease."
He added that the team planned to screen more skeletal material from all over Europe as a next step.