ecent declines, extinctions, and range contractions of vertebrates have disrupted important ecological functions, particularly on island systems. Restoration of ecological function requires rewilding of key species, often in the face of ongoing stressors, within heterogeneous and fragmented landscapes. As a result, successfully restoring ecological function is difficult, but islands provide an opportunity to develop strategies for restoration, which may then be applied across larger areas. Here, we assess the effect of frugivore loss as a result of the invasive brown treesnake (Boiga irregularis) on the island of Guam and develop a strategy for rewilding the island given the continuing presence of the snake. To determine how frugivores affect forest composition and structure, we compared Guam to nearby islands with vertebrate seed dispersers, using surveys, manipulative experiments, and a forest model. We demonstrate that Guam's forests will become less diverse and less able to recover from disturbance without vertebrate seed dispersers. We then developed a strategy to restore seed dispersal to Guam's forests. First, we assessed the seed dispersal effectiveness of 5 native birds, the Mariana Fruit Bat (Pteropus mariannus), and two non-native mammals currently present on Guam - the feral pig (Sus scrofa) and black rat (Rattus rattus). The native avian frugivores varied dramatically in their effectiveness, but the two bird species that had the broadest diets, positive impact on germination, and extensive movement across habitat types were selected as preferred candidates for reintroduction. While the non-native pig effectively dispersed seeds, the non-native rat did not; the pig may be a useful disperser in the short-term in particular habitats where it has fewer negative impacts. We then used a spatially-explicit model to identify the highest priority areas for rewilding the three frugivore species to restore ecological function, and the associated costs of invasive species control. Restoration of vertebrate seed dispersers in the presence of invasive predators may be an achievable goal on Guam, and could serve as a guide for rewilding efforts in other places that are under threat.