Populations in Mongolia from the late second millennium B.C.E. through the Mongol Empire are traditionally assumed, by archaeologists and historians, to have maintained a highly specialized horse-facilitated form of mobile pastoralism. Until recently, a dearth of direct evidence for prehistoric human diet and subsistence economies in Mongolia has rendered systematic testing of this view impossible. Here, we present stable carbon and nitrogen isotope measurements of human bone collagen, and stable carbon isotope analysis of human enamel bioapatite, from 137 well-dated ancient Mongolian individuals spanning the period c. 4400 B.C.E. to 1300 C.E. Our results demonstrate an increase in consumption of C4 plants beginning at c. 800 B.C.E., almost certainly indicative of millet consumption, an interpretation supported by archaeological evidence. The escalating scale of millet consumption on the eastern Eurasian steppe over time, and an expansion of isotopic niche widths, indicate that historic Mongolian empires were supported by a diversification of economic strategies rather than uniform, specialized pastoralism.