Dairy pastoralism is integral to contemporary and past lifeways on the eastern Eurasian steppe, facilitating survival in agriculturally challenging environments. While previous research has indicated that ruminant dairy pastoralism was practiced in the region by circa 1300 BC, the origin, extent and diversity of this custom remain poorly understood. Here, we analyse ancient proteins from human dental calculus recovered from geographically diverse locations across Mongolia and spanning 5,000 years. We present the earliest evidence for dairy consumption on the eastern Eurasian steppe by circa 3000 BC and the later emergence of horse milking at circa 1200 BC, concurrent with the first evidence for horse riding. We argue that ruminant dairying contributed to the demographic success of Bronze Age Mongolian populations and that the origins of traditional horse dairy products in eastern Eurasia are closely tied to the regional emergence of mounted herding societies during the late second millennium BC.