We have collated and reviewed published records of the genera Panicum and Setaria (Poaceae), including the domesticated millets Panicum miliaceum L. (broomcorn millet) and Setaria italica (L.) P. Beauv. (foxtail millet) in pre-5000 cal b.c. sites across the Old World. Details of these sites, which span China, central-eastern Europe including the Caucasus, Iran, Syria and Egypt, are presented with associated calibrated radiocarbon dates. Forty-one sites have records of Panicum (P. miliaceum, P. cf. miliaceum, Panicum sp., Panicum type, P. capillare (?) and P. turgidum) and 33 of Setaria (S. italica, S. viridis, S. viridis/verticillata, Setaria sp., Setaria type). We identify problems of taphonomy, identification criteria and reporting, and inference of domesticated/wild and crop/weed status of finds. Both broomcorn and foxtail millet occur in northern China prior to 5000 cal b.c.; P. miliaceum occurs contemporaneously in Europe, but its significance is unclear. Further work is needed to resolve the above issues before the status of these taxa in this period can be fully evaluated. ELECTRONIC SUPPLEMENTARY MATERIAL: The online version of this article (doi:10.1007/s00334-008-0187-1) contains supplementary material, which is available to authorized users.