Top predators often have powerful direct effects on prey populations, but whether these direct effects propagate to the base of terrestrial food webs is debated. There are few examples of trophic cascades strong enough to alter the abundance and composition of entire plant communities. We show that the introduction of arctic foxes (Alopex lagopus) to the Aleutian archipelago induced strong shifts in plant productivity and community structure via a previously unknown pathway. By preying on seabirds, foxes reduced nutrient transport from ocean to land, affecting soil fertility and transforming grasslands to dwarf shrub/forb-dominated ecosystems.