Reported declines of pollinator populations around the world have led to increasing concerns about the consequences of pollination as a critical ecosystem function and service. Pollination could be maintained through compensation if remaining pollinators increase their contribution or if novel species are recruited as pollinators, but empirical evidence of this compensation is so far lacking. Using a natural experiment in New Zealand where endemic vertebrate pollinators still occur on one offshore island reserve despite their local extinction on the adjacent North Island, we investigated whether compensation could maintain pollination in the face of pollinator extinctions. We show that two recently arrived species in New Zealand, the invasive ship rat (Rattus rattus) and the recent colonist silvereye (Zosterops lateralis; a passerine bird), at least partly maintain pollination for three forest plant species in northern New Zealand, and without this compensation, these plants would be significantly more pollen-limited. This study provides empirical evidence that widespread non-native species can play an important role in maintaining ecosystem functions, a role that needs to be assessed when planning invasive species control or eradication programs.