Abstract The evolution of traits involved in ecological interactions such as predator-prey, host-parasite, and plant-pollinator interactions, are likely to be shaped by the phylogenetic history of both parties. We develop generalized linear mixed-effects models (GLMM) that estimate the effect of both parties' phylogenetic history on trait evolution, both in isolation but also in terms of how the two histories interact. Using data on the incidence and abundance of 206 flea species on 121 mammal species, we illustrate our method and compare it to previously used methods for detecting host-parasite coevolution. At large spatial scales we find that the phylogenetic interaction effect was substantial, indicating that related parasite species were more likely to be found on related host species. At smaller spatial scales, and when sampling effort was not controlled for, phylogenetic effects on the number and types of parasite species harbored by hosts were found to dominate. We go on to show that in situations where these additional phylogenetic effects exist, then previous methods have very high Type I error rates when testing for the phylogenetic interaction. Our GLMM method represents a robust and reliable approach to quantify the phylogenetic effects of traits determined by, or defined by, ecological interactions and has the advantage that it can easily be extended and interpreted in a broader context than existing permutation tests.