Charred grass seeds recovered by flotation from the late Upper Paleolithic Shizitan Locality 9 site in Shanxi province, China, are examined in relation to claims based on starch grain and phytolith analysis of early millet domestication and Neolithic plant foods in North China. Small numbers of wild millet (Paniceae tribe) grasses and goosefoot (Chenopodium sp.) seeds provide the first specific macrobotanical evidence for the association of these important plants with people in China during the late Paleolithic. Wild Setaria and Echinochloa spp. are present between 13,800 and 11,600 cal. BP, almost 4000 years before the earliest evidence of unequivocally domesticated millet macrofossils in the Yellow River region by c. 8000–7600 cal. BP. In fact, seed evidence for the process of foxtail millet domestication in North China has not been available until now, and these are the only late Upper Paleolithic seeds ever recovered from North China. This study suggests that domestication-related traits in foxtail millet were gradually established over several millennia.