Global declines of large carnivores have reduced the ‘landscape of fear’ that constrains the behaviour of other species. In recent years, active and passive trophic rewilding have potentially begun restoring these lost top-down controls. The Tasmanian devil (Sarcophilus harrisii) has declined severely due to a novel transmissible cancer. In response to extinction fears, devils were introduced to the devil-free Maria Island, where their abundance rapidly increased. We tested how this introduction influenced risk-sensitive foraging in the common brushtail possum (Trichosurus vulpecula), a major prey species for devils, using giving-up densities (GUDs). Before the introduction of devils, possum GUDs on Maria Island were indistinguishable from the long-diseased region of Tasmania, where devils have been rare since ~2000. Three years after devil introduction, GUDs were 64% higher on Maria Island than the control region, demonstrating that after an initial period of high mortality, possums quickly adopted risk-sensitive foraging behaviours. Devil activity across Maria Island was variable, leading to a heterogeneous landscape of fear and highlighting that top predators must be at functional densities to elicit behavioural responses from prey. Our study provides strong evidence that top predators modify the behaviour of prey by instilling fear, causing rapid ecological change following recoveries.