Disturbances and ecosystem recovery from disturbance both involve numerous processes that operate on multiple spatial and temporal scales. Few studies have investigated how gradients of disturbance intensity and ecosystem responses are distributed across multiple spatial resolutions and also how this relationship changes through time during recovery. We investigated how cover of non-native species and soil-aggregate stability (a measure of vulnerability to erosion by water) in surface and subsurface soils varied spatially during grazing by burros and cattle and whether patterns in these variables changed after grazer removal from Mojave National Preserve, California, USA. We compared distance from water and number of ungulate defecations — metrics of longer-term and recent grazing intensity, respectively, — as predictors of our response variables. We used information-theoretic analyses to compare hierarchical linear models that accounted for important covariates and allowed for interannual variation in the disturbance–response relationship at local and landscape scales. Soil stability was greater under perennial vegetation than in bare interspaces, and surface soil stability decreased with increasing numbers of ungulate defecations. Stability of surface samples was more affected by time since removal of grazers than was stability of subsurface samples, and subsurface soil stability in bare spaces was not related to grazing intensity, time since removal, or any of our other predictors. In the high rainfall year (2003) after cattle had been removed for 1–2 years, cover of all non-native plants averaged nine times higher than in the low-rainfall year (2002). Given the heterogeneity in distribution of large-herbivore impacts that we observed at several resolutions, hierarchical analyses provided a more complete understanding of the spatial and temporal complexities of disturbance and recovery processes in arid ecosystems.