While North China is one of the earliest independent centers for cereal domestication in the world, the earliest stages of the long process of agricultural origins remain unclear. While only millets were eventually domesticated in early sedentary societies there, recent archaeobotanical evidence reported here indicates that grasses from the Paniceae (including millets) and Triticeae tribes were exploited together by foraging groups from the Last Glacial Maximum to the mid-Holocene. Here we explore how and why millets were selected for domestication while Triticeae were abandoned. We document the different exploitation and cultivation trajectories of the two tribes employing ancient starch data derived from nine archaeological sites dating from 25,000 to 5500 cal BP (LGM through mid-Holocene) in North China. With this diachronic overview, we can place the trajectories into the context of paleoclimatic reconstructions for this period. Entering the Holocene, climatic changes increased the yield stability, abundance, and availability of the wild progenitors of millets, with growing conditions increasingly favoring millets while becoming more unfavorable for grasses of the Triticeae tribe. We thus hypothesize that climate change played a critical role in the selection of millet species for domestication in North China, with early domestication evidenced by 8700 cal BP.