Milk from domestic cows has been a valuable food source for over 8,000 years, especially in lactose-tolerant human societies that exploit dairy breeds. We studied geographic patterns of variation in genes encoding the six most important milk proteins in 70 native European cattle breeds. We found substantial geographic coincidence between high diversity in cattle milk genes, locations of the European Neolithic cattle farming sites (>5,000 years ago) and present-day lactose tolerance in Europeans. This suggests a gene-culture coevolution between cattle and humans.