The role of wind in changing the spatial heterogeneity of soil resources in erosion-dominated semiarid ecosystems is well known. Yet the effect of windblown sediment deposition on soil nutrient distribution and ecosystem dynamics at local and landscape scales has received little attention. We examined the effects of enhanced sediment deposition on the spatial distribution of soil nutrients at the Jornada Experimental Range, southern New Mexico. Enhanced sediment deposition was obtained as a result of grass cover reduction in the upwind portion of the experiment in two sites co-dominated by mesquite and one of two grass species with different morphologies. The spatial characteristics of soil available nitrogen (including ammonium, nitrite, and nitrate), phosphate, potassium, and calcium were quantified using a variety of traditional and geostatistical analyses. Our results showed that enhanced deposition led to considerable reduction in both mean soil nutrient concentrations and coefficients of variation over a two-year period (2004–2006). Given the observed increase in the scale of spatial dependence for available nitrogen, but not for potassium, phosphate, and calcium following enhanced sediment deposition, we suggest that soil available nitrogen may be particularly responsive to increased aeolian activities due to livestock grazing and other anthropogenic activities that remove vegetation. Our study further suggests that soil particles deposited in the downwind area may be “nutrient-imbalanced.” Specifically, the lower-than-normal available nitrogen concentrations in the wind-deposited soils may inhibit the growth of grasses and the germination of seeds. For wind-erodible ecosystems found in southern New Mexico, structures of Bouteloua-dominated communities may be particularly susceptible to change under enhanced soil erosion conditions.