For more than 70 years, red sandstones of the Gobi Desert have yielded abundant articulated skeletons of Late Cretaceous dinosaurs, lizards, and mammals. At Ukhaa Tolgod, structureless sandstones are the only fossiliferous facies, and we present new evidence for deposition on dune-sand–sourced alluvial fans that were built at the margins of stabilized eolian bedforms during mesic climatic episodes. In laterally and vertically adjacent large-scale eolian cross-strata in which skeletons are absent, we have found abundant tracks of dinosaurs that walked on sparsely vegetated dunes that were active under xeric conditions. Our study of calcareous concretions in vaguely bedded eolian sandstones suggests that bedding was nearly destroyed by burrowing invertebrates and trampling dinosaurs. The accumulation of illuvial clays and pedogenic calcite in these sediments reduced infiltration of rainwater and, with attendant climatic change and heavy rainfall events, led to fan development.