While species interactions are fundamental for linking biodiversity to ecosystem functioning and for conservation, large-scale empirical data are lacking for most species and ecosystems. Accumulating evidence suggests that trophic interactions are predictable from available functional trait information, but we have yet to understand how well we can predict interactions across large spatial scales and food webs. Here, we built a model predicting predator-prey interactions based on functional traits for European vertebrates. We found that even models calibrated with very few known interactions (100 out of 71k) estimated the entire food web reasonably well. However, predators were easier to predict than prey, with prey in some clades being particularly difficult to predict (e.g., fowls and storks). Local food web connectance was also consistently over-estimated. Our results demonstrate the potential for filling gaps in sparse food webs, an important step towards a better description of biodiversity with strong implications for conservation planning.