Given that many exotic plant species throughout the world are having large ecological and economic effects, it is vital to understand the forces that mediate their success in novel landscapes. Both native herbivores and recipient ecosystems can have substantial effects on the performance of exotic plant species, and may interact with each other or vary in their effects over time. Unfortunately, few studies have evaluated the importance of these kinds of context-dependent effects. Here, we use a 17-year-old exclosure experiment stratified across a coastal grassland in northern California to address the relative importance of a reintroduced mammalian herbivore, tule elk (Cervus canadensis nannodes), and environmental heterogeneity in mediating the growth, abundance, and recruitment of a problematic grass invader, Holcus lanatus. We found that elk reduced Holcus abundance, aboveground biomass, percent cover, frequency, and seedling recruitment, but that these effects often varied among habitat types, with effects being greater in open grasslands than shrub-dominated grasslands. The performance of Holcus populations also varied significantly among habitat types, with the invader usually having the greatest success in Baccharis-dominated grasslands. Our results suggest that environmental heterogeneity had much greater influence on Holcus success than elk, and that these effects were due largely to soil pH and moisture. The negative effects of elk on Holcus appeared after 4 years and did not intensify after an additional 13 years. Furthermore, despite their negative effects, these prominent herbivores did not prevent the spread of Holcus into previously uninvaded areas. Our research highlights the importance of assessing the individual and interactive effects of native herbivores and environmental heterogeneity on the success of invasive, exotic plant species. It emphasizes the reality that the negative effects of herbivores on exotic plant species will often vary across heterogeneous landscapes and may be insufficient to prevent the expansion of these invaders.