We investigated spatial variation in the phylogenetic structure of host spectra in fleas parasitic on small mammals. Measures of phylogenetic host specificity ((phylogenetic species clustering (PSC) and phylogenetic species variability (PSV)) varied significantly more between than within flea species, but the proportion of variation which accounted for among-species differences was low. In 13 of 18 common flea species, at least one of the indices of the phylogenetic structure of regional host spectra revealed a significantly positive association with the phylogenetic structure of regional host assemblage, while relationships between PSC or PSV of the regional host spectrum and the distance from either the region of a flea's maximal abundance or latitude were not supported. Overall, results of this study demonstrated that although the degree of phylogenetic host specificity in fleas can be considered as a true attribute of a flea species, it is highly spatially variable, with phylogenetic structure of the surrounding host pool being the main reason behind this variation.