Many arid grassland communities are changing from grass dominance to shrub dominance, but the mechanisms involved in this conversion process are not completely understood. Aeolian processes likely contribute to this conversion from grassland to shrubland. The purpose of this research is to provide information regarding how vegetation changes occur in an arid grassland as a result of aeolian sediment transport. The experimental design included three treatment blocks, each with a 25 × 50 m area where all grasses, semi-shrubs, and perennial forbs were hand removed, a 25 × 50 m control area with no manipulation of vegetation cover, and two 10 × 25 m plots immediately downwind of the grass-removal and control areas in the prevailing wind direction, 19° north of east, for measuring vegetation cover. Aeolian sediment flux, soil nutrients, and soil seed bank were monitored on each treatment area and downwind plot. Grass and shrub cover were measured on each grass-removal, control, and downwind plot along continuous line transects as well as on 5 × 10 m subplots within each downwind area over four years following grass removal. On grass-removal areas, sediment flux increased significantly, soil nutrients and seed bank were depleted, and Prosopis glandulosa shrub cover increased compared to controls. Additionally, differential changes for grass and shrub cover were observed for plots downwind of vegetation-removal and control areas. Grass cover on plots downwind of vegetation-removal areas decreased over time (2004–2007) despite above average rainfall throughout the period of observation, while grass cover increased downwind of control areas; P. glandulosa cover increased on plots downwind of vegetation-removal areas, while decreasing on plots downwind of control areas. The relationships between vegetation changes and aeolian sediment flux were significant and were best described by a logarithmic function, with decreases in grass cover and increases in shrub cover occurring with small increases in aeolian sediment flux.