Grasslands have been pivotal in the development of domestic herbivore breeding since the Neolithic and are nowadays the most widespread agricultural land-use over Europe. We have demonstrated that the genealogy of natural Lolium perenne (perennial ryegrass), from permanent grasslands across Europe and the Fertile Crescent, can be traced back to the pre-Holocene epoch (> 12 kya). Demographic events in this species, as reconstructed from genetic data, can be explained by the changing climatic conditions during Quaternary glaciations in Europe. Specific population splits and admixtures fit historical sea level changes across the Mediterranean basin. According to our estimations, population expansion across continental Europe took place during the Würm glaciation (12-110 kya), a cooling period that decreased the dominance of trees in favor of herbs, and notably grasses. The development of agriculture and herbivore breeding that started in the late Holocene (3.5 kya) and caused an increase in the abundance of grasses across Europe did not impact the genetic structure of Lolium perenne at continental scale. Furthermore, our results reveal little differentiation between cultivars released by contemporary plant breeding and natural strains of L. perenne, pointing to the very recent start of intensive human directional selection in herbage grasses. We expose that natural grasslands harbor wide genetic variability at continental scale that has enabled grasses to survive extreme climatic changes across millennia. This genetic variability has been underused by recent breeding activities and constitute valuable standing genetic variation for future adaptation of grasslands to Climate Change, safeguarding the agricultural services they provide.