The initial movement of herders and livestock into the eastern steppe is of great interest, as this region has long been home to pastoralist groups. Due to a paucity of faunal remains, however, it has been difficult to discern the timing of the adoption of domesticated ruminants and horses into the region, though recent research on ancient dairying has started to shed new light on this history. Here we present proteomic evidence for shifts in dairy consumption in the Altai Mountains, drawing on evidence from sites dating from the Early Bronze to the Late Iron Age. We compare these finds with evidence for the rise of social complexity in western Mongolia, as reflected in material remains signaling population growth, the establishment of structured cemeteries, and the erection of large monuments. Our results suggest that the subsistence basis for the development of complex societies began at the dawn of the Bronze Age, with the adoption of ruminant livestock. Investments in pastoralism intensified over time, enabling a food production system that sustained growing populations. While pronounced social changes and monumental constructions occurred in tandem with the first evidence for horse dairying, ~1350 cal BCE, these shifts were fueled by a long-term economic dependence on ruminant livestock. Therefore, the spread into the Mongolian Altai of herds, and then horses, resulted in immediate dietary changes, with subsequent social and demographic transformations occurring later.