With increasing biotic introductions, there is a great need for predictive tools to anticipate which new trophic interactions will develop and which will not. Phylogenetic constraint of interactions in both native and novel food webs can make some novel interactions predictable. However, many food webs are sparsely sampled, or may include inaccurate interactions. In such cases, it is unclear whether modeling methods are still useful to anticipate novel interactions. We ran bootstrap simulations of host-use models on a Lepidoptera–plant data set to remove native trophic records or add erroneous records in order to observe the effect of missing or erroneous data on the prediction of interactions with novel plants. We found that the model was robust to a large amount of missing interaction records, but lost predictive power with the addition of relatively few erroneous interaction records. The loss of predictive power with missing records was due to inaccuracy in estimating phylogenetic distance between native and novel hosts. Removal of interaction records proportionally to their encounter frequency in the field had little effect on the loss of predictive power. Host-use models may have immediate value for predicting novel interactions from large, but sparsely sampled databases of trophic interactions.