Many soils in southeastern Utah are protected from surface disturbance by biological soil crusts that stabilize soils and reduce erosion by wind and water. When these crusts are disturbed by land use, soils become susceptible to erosion. In this study, we compare a never-grazed grassland in Canyonlands National Park with two historically grazed sites with similar geologic, geomorphic, and geochemical characteristics that were grazed from the late 1800s until 1974. We show that, despite almost 30 years without livestock grazing, surface soils in the historically grazed sites have 38–43% less silt, as well as 14– 51% less total elemental soil Mg, Na, P, and Mn content relative to soils never exposed to livestock disturbances. Using magnetic measurement of soil magnetite content (a proxy for the stabilization of far-traveled eolian dust) we suggest that the differences in Mg, Na, P, and Mn are related to wind erosion of soil fine particles after the historical disturbance by livestock grazing. Historical grazing may also lead to changes in soil organic matter content including declines of 60–70% in surface soil C and N relative to the never-grazed sites. Collectively, the differences in soil C and N content and the evidence for substantial rock-derived nutrient loss to wind erosion implies that livestock grazing could have long-lasting effects on the soil fertility of native grasslands in this part of southeastern Utah. This study suggests that nutrient loss due to wind erosion of soils should be a consideration for management decisions related to the long-term sustainability of grazing operations in arid environments.