To measure and manage for C sequestration in heterogeneous rangeland systems, we need to more fully understand spatial patterns of soil resources. Spatial distributions of aggregate stability and soil carbon were investigated in a semiarid rangeland in New Mexico, U.S.A. Soil was analyzed from plant interspaces, black grama (Bouteloua eriopoda (Torr.) Torr.), and mesquite (Prosopis glandulosa Torr.) in a landscape-replicated study. Aggregate stability at the 250 micro meter scale, carbonate C, organic C and N, C:N ratio, and glomalin, were all highest under mesquite. Soil C:N ratio was the best predictor of aggregate stability. Estimates of metric tons of C per hectare in the top 10 cm were highly variable at patch and landscape scales, varying from 10.5 under mesquite to 3.0 in interspaces. High variability of aggregate stability and soil C has important implications for C sequestration. We argue that this multi-scale soil heterogeneity must be considered when measuring and managing for C sequestration.