Humans are altering the global distributional ranges of plants, while their co-evolved herbivores are frequently left behind. Native herbivores often colonise non-native plants, potentially reducing invasion success or causing economic loss to introduced agricultural crops. We developed a predictive model to forecast novel interactions and verified it with a data set containing hundreds of observed novel plant–insect interactions. Using a food network of 900 native European butterfly and moth species and 1944 native plants, we built an herbivore host-use model. By extrapolating host use from the native herbivore–plant food network, we accurately forecasted the observed novel use of 459 non-native plant species by native herbivores. Patterns that governed herbivore host breadth on co-evolved native plants were equally important in determining non-native hosts. Our results make the forecasting of novel herbivore communities feasible in order to better understand the fate and impact of introduced plants.