Cenozoic climate has changed markedly from a warm, wet climate to the present cool, dry glacial-interglacial cycles. The largest of these cooling steps is thought to have taken place across the Eocene-Oligocene transition. Terrestrial airborne eolian loess is a direct result of land aridification; therefore, the prolonged formation of thick eolian loess deposits provides a key to aridification history in the geological past. However, the oldest eolian loess in the Asian interior has been dated to only 25–22 Ma. Here we present new sedimentological, geochemical, and magnetostratigraphic data from Cenozoic sections in southwestern Mongolia to show that the earliest eolian dust accumulation occurred by 34 Ma, ∼10 m.y. earlier than currently believed. We suggest that this oldest eolian dust accumulation provides direct evidence for enhanced aridification across the Eocene-Oligocene transition in Central Asia; this is explicable by reduced moisture transport caused by prevailing westerlies during retreat of the Neotethys Ocean. These climatic changes were related to the changing regional plate configuration as well as to global cooling and ice-sheet growth in Antarctica.