Invasive vertebrate predators are directly responsible for the extinction or decline of many vertebrate species, but their indirect impacts often go unmeasured, potentially leading to an underestimation of their full impact. When invasives extirpate functionally important mutualists, dependent species are likely to be affected as well. Here, we show that the invasive brown treesnake, directly responsible for the extirpation of forest birds from the island of Guam, is also indirectly responsible for a severe decline in plant recruitment as a result of disrupting the fruit-frugivore mutualism. To assess the impact of frugivore loss on plants, we compare seed dispersal and recruitment of two fleshy-fruited tree species on Guam and three nearby islands with intact disperser communities. We conservatively estimate that the loss of frugivorous birds caused by the brown treesnake may have caused a 61-92% decline in seedling recruitment. This case study highlights the potential for predator invasions to cause indirect, pervasive and easily overlooked interaction cascades.