The accurate characterization of near-surface winds is critical to our understanding of past and modern climate. Dust lofted by these winds has the potential to modify surface and atmospheric conditions as well as ocean biogeochemistry. Stony deserts, low dust emitting regions today, represent expansive areas where variations in surficial geology through time may drastically impact near-surface conditions. Here we use the Weather Research and Forecasting (WRF) model over the western Gobi Desert to demonstrate a previously undocumented process between wind-driven landscape evolution and boundary layer conditions. Our results show that altered surficial thermal properties through winnowing of fine-grained sediments and formation of low-albedo gravel-mantled surfaces leads to an increase in near-surface winds by up to 25%; paradoxically, wind erosion results in faster winds regionally. This wind-albedo-wind feedback also leads to an increase in the frequency of hours spent at higher wind speeds, which has implications for dust emission potential.