Although broomcorn and foxtail millet are among the earliest staple crop domesticates, their spread and impacts on demography remain controversial, mainly because of the use of indirect evidence. Bayesian modeling applied to a dataset of new and published radiocarbon dates derived from domesticated millet grains suggests that after their initial cultivation in the crescent around the Bohai Sea ca. 5800 BCE, the crops spread discontinuously across eastern Asia. Our findings on the spread of millet that intensified during the fourth millennium BCE coincide with published dates of the expansion of the Sino-Tibetan languages from the Yellow River basin. In northern China, the spread of millet-based agriculture supported a quasi-exponential population growth from 6000 to 2000 BCE. While growth continued in northeastern China after 2000 BCE, the Upper/Middle Yellow River experienced decline. We propose that this pattern of regional divergence is mainly the result of internal and external anthropogenic factors.