The effect of environmental change on ecosystems is mediated by species interactions. Environmental change may remove or add species and shift life-history events, altering which species interact at a given time. However, environmental change may also reconfigure multispecies interactions when both species composition and phenology remain intact. In a Caribbean island system, a major manifestation of environmental change is seaweed deposition, which has been linked to eutrophication, overfishing, and hurricanes. Here, we show in a whole-island field experiment that without seaweed two predators--lizards and ants--had a substantially greater-than-additive effect on herbivory. When seaweed was added to mimic deposition by hurricanes, no interactive predator effect occurred. Thus environmental change can substantially restructure food-web interactions, complicating efforts to predict anthropogenic changes in ecosystem processes.