Broomcorn millet (Panicum miliaceum L.) is not one of the founder crops domesticated in Southwest Asia in the early Holocene, but was domesticated in northeast China by 6000 bc. In Europe, millet was reported in Early Neolithic contexts formed by 6000 bc, but recent radiocarbon dating of a dozen 'early' grains cast doubt on these claims. Archaeobotanical evidence reveals that millet was common in Europe from the 2nd millennium bc, when major societal and economic transformations took place in the Bronze Age. We conducted an extensive programme of AMS-dating of charred broomcorn millet grains from 75 prehistoric sites in Europe. Our Bayesian model reveals that millet cultivation began in Europe at the earliest during the sixteenth century bc, and spread rapidly during the fifteenth/fourteenth centuries bc. Broomcorn millet succeeds in exceptionally wide range of growing conditions and completes its lifecycle in less than three summer months. Offering an additional harvest and thus surplus food/fodder, it likely was a transformative innovation in European prehistoric agriculture previously based mainly on (winter) cropping of wheat and barley. We provide a new, high-resolution chronological framework for this key agricultural development that likely contributed to far-reaching changes in lifestyle in late 2nd millennium bc Europe.