1) Patterns of landscape heterogeneity are crucial to the maintenance of biodiversity in shrublands and grasslands, yet management practices in these ecosystems typically seek to homogenize landscapes. Furthermore, there is limited understanding of how the interaction of ecological processes, such as fire and grazing, affects patterns of heterogeneity at different spatial scales. 2) We conducted research in Artemisia filifolia (Asteraceae) shrublands located in the southern Great Plains of North America to determine the effect of restoring the fire-grazing interaction on vegetation structure. Data were collected for 3 years in replicated pastures grazed by cattle Bos taurus where the fire-grazing interaction had been restored (fire and grazing = treatment pastures) and in pastures that were grazed but remained unburned (grazing only, no fire = control pastures). The effect of the fire-grazing interaction on heterogeneity (variance) of vegetation structure was assessed at scales from 12Â·5 m2 to 609 ha. 3) Most measurements of vegetation structure within treatment pastures differed from control pastures for 1-3 years after being burned but were thereafter similar to the values found in unburned control pastures. 4) Treatment pastures were characterized by a lower amount of total heterogeneity and a lower amount of heterogeneity through time. 5) Heterogeneity of vegetation structure tended to decrease as the scale of measurement increased in both treatment and control pastures. There was deviation from this trend, however, in the treatment pastures that exhibited much higher heterogeneity at the patch scale (mean patch size = 202 ha) of measurement, the scale at which patch fires were conducted. 6) Synthesis and applications. Vegetation structure in A. filifolia shrublands of our study was readily altered by the fire-grazing interaction but also demonstrated substantial resilience to these effects. The fire-grazing interaction also changed the total amount of heterogeneity characterizing this system, the scale at which heterogeneity in this system was expressed and the amount of heterogeneity expressed through time. Land managers seeking to impose a shifting mosaic of heterogeneity on this vegetation type can do so by restoring the fire-grazing interaction with potential conservation benefits similar to what has been achieved in other ecosystems where historic cycles of disturbance and rest have been restored.