We tested the hypothesis that compositional and/or phylogenetic dissimilarity of host assemblages affect compositional and/or phylogenetic dissimilarity of parasite assemblages, to different extents depending on scale, using regional surveys of fleas parasitic on small mammals from 4 biogeographical realms. Using phylogenetic community dissimilarity metric, we calculated the compositional and phylogenetic dissimilarity components between all pairs of host and parasite communities within realms and hemispheres. We then quantified the effect of compositional or phylogenetic dissimilarity in host regional assemblages, and geographical distance between assemblages, on the compositional or phylogenetic dissimilarity of flea regional assemblages within a realm, respectively. The compositional dissimilarity in host assemblages strongly affected compositional dissimilarity in flea assemblages within all realms and within both hemispheres. However, the effect of phylogenetic dissimilarity of host assemblages on that of flea assemblages was mostly confined to the Neotropics and Nearctic, but was detected in both the Old and New World at the higher scale, possibly because of phylogenetic heterogeneity in flea and host faunas between realms. The clearer effect of the compositional rather than the phylogenetic component of host community dissimilarity on flea community dissimilarity suggests important roles for host switching and ecological fitting during the assembly history of flea communities.