Global warming may affect most organisms and their interactions. Theory and simple mesocosm experiments suggest that consumer top-down control over primary producer biomass should strengthen with warming, since consumer respiration increases faster with warming than plant photosynthesis. However, these predictions have so far not been tested on natural communities that have experienced warming over many generations. Natural systems display a higher diversity, heterogeneity and complexity than mesocosms, which could alter predicted effects of warming. Here we used an artificially heated part of the northern Baltic Sea (the Forsmark Biotest basin) to test how warming influences trophic interactions in a shallow coastal food web with four trophic levels: omnivorous fish, invertivorous fish, herbivorous invertebrates, and filamentous macroalgae. Monitoring of fish assemblages over six years showed that small invertivorous fish (gobiids, sticklebacks and minnows) were much less abundant in the heated basin than in unheated references areas. Stomach content analyses of the dominating omnivorous fish - Eurasian perch Perca fluviatilis - revealed a strikingly different diet within and outside the Biotest basin; gammarid crustaceans were the dominating prey at heated sites, whereas invertivorous fish (e.g. gobiids) dominated at unheated sites. A 45-day cage experiment showed that fish exclusion did not affect the biomass of algal herbivores (gastropods and gammarids), but reduced algal biomass in heated sites (but not unheated). This suggests that warming induced a trophic cascade from fish to algae, and that this effect was mediated by predator-induced changes in herbivore behavior, rather than number. Overall, our study suggests that warming has effectively compressed the food chain from four to three trophic levels (algae, gammarids and perch), which have benefitted the primary producers by reducing grazing pressure. Consequently, warming appears to have restructured this coastal food web through a combination of direct (physiological) and indirect (species interactions) effects.