Responses of plant communities to mammalian herbivores vary widely, due to variation in plant species composition, herbivore densities, forage preferences, soils, and climate. In this study, we evaluated simultaneous changes in 11 plant assemblages on the 100,000 ha Sevilleta National Wildlife Refuge (SNWR) in central New Mexico, USA, over a 20-yr period following removal of the major mammalian herbivores (livestock and prairie dogs) in 1972-1975. Thirty study sites were established in 1976 within and outside of the SNWR, and these sites were resampled in 1986 and 1996 using line transect methods. At the landscape scale, repeated measures ANOVA of percentage cover measurements showed no significant overall net changes in total perennial plant basal cover, either with or without herbivores present; however, there was an overall increase in annual forbs and plant litter from 1976 to 1996. At the site scale, significant changes in species composition and dominance were observed both through time and across the SNWR boundary; each plant assemblage exhibited varying degrees of change, with sites dominated by Bouteloua eriopoda (black grama grass) being the most dynamic and sites dominated by Scleropogon brevifolius (burro grass) being the most persistent. Species-specific changes also were observed across multiple sites: B. eriopoda cover increased while Gutierrezia sarothrae (a small, short-lived shrub) greatly decreased. The non-uniform, multi-directional changes of the different plant assemblages acted to prevent detection of overall changes in perennial vegetation at the landscape level. Some plant assemblages displayed significant changes after removal of herbivores, while others appeared to respond primarily to climate dynamics. Certain species (e.g., G. sarothrae) that were not preferred by livestock or prairie dogs showed overall declines during drought periods, while other preferred species (e.g., B. eriopoda) exhibited widespread increases during wetter periods regardless of herbivore presence. Therefore, the vegetation dynamics cannot be attributed solely to removal of mammalian herbivores, and in some cases can be explained by short- and long-term fluctuations in climate. These results emphasize the variety of responses of different plant assemblages to mammalian herbivores under otherwise similar climatic conditions, and illustrate the value of site- and landscape-scale approaches to understanding the impacts of plant-herbivore interactions.