Restoration of damaged ecosystems through invasive species removal and native species conservation is an increasingly common practice in biodiversity conservation. Estimating the degree of ecosystem response attributable specifically to eradication of exotic herbivores versus restoration of native herbivores is often difficult and is complicated by concurrent temporal changes in other factors, especially climate. We investigated the interactive impacts of native mega-herbivores (giant tortoises) and the eradication of large alien herbivores (goats) on vegetation productivity across the Galapagos Archipelago. We examined archipelago-wide patterns of Normalized Difference Vegetation Index (NDVI) as a proxy for vegetation productivity between 2001 and 2015 and evaluated how goat and historical and current tortoise occurrence influenced productivity. We used a breakpoint analysis to detect change in trends in productivity from five targeted areas following goat eradication. We found a positive association between tortoise occurrence and vegetation productivity and a negative association with goat occurrence. We also documented an increase in plant productivity following goat removal with recovery higher in moister regions than in arid region, potentially indicating an alternate stable state has been created in the latter. Climate variation also contributed to the detected improvement in productivity following goat eradication, sometimes obscuring the effect of eradication but more usually magnifying it by up to 300%. Our work offers perspectives regarding the effectiveness and outcomes of eradicating introduced herbivores and re-introducing native herbivores, and the merits of staging them simultaneously in order to restore critical ecosystem processes such as vegetation productivity.