The bacteria Yersinia pestis is the etiological agent of plague and has caused human pandemics with millions of deaths in historic times. How and when it originated remains contentious. Here, we report the oldest direct evidence of Yersinia pestis identified by ancient DNA in human teeth from Asia and Europe dating from 2,800 to 5,000 years ago. By sequencing the genomes, we find that these ancient plague strains are basal to all known Yersinia pestis. We find the origins of the Yersinia pestis lineage to be at least two times older than previous estimates. We also identify a temporal sequence of genetic changes that lead to increased virulence and the emergence of the bubonic plague. Our results show that plague infection was endemic in the human populations of Eurasia at least 3,000 years before any historical recordings of pandemics. Display omitted •Yersinia pestis was common across Eurasia in the Bronze Age•The most recent common ancestor of all Y. pestis was 5,783 years ago•The ymt gene was acquired before 951 cal BC, giving rise to transmission via fleas•Bronze Age Y. pestis was not capable of causing bubonic plague The plague-causing bacteria Yersinia pestis infected humans in Bronze Age Eurasia, three millennia earlier than any historical records of plague, but only acquired the genetic changes making it a highly virulent, flea-borne bubonic strain ∼3,000 years ago.