Evolutionary trends in the evolution of host specificity have been the focus of much discussion but little rigorous empirical testing. On the one hand, specialization is often presumed to lead irreversibly into evolutionary dead ends and little diversification; this would mean that generalists might evolve into specialists, but not vice versa. On the other hand, low host specificity may limit the risk of extinction and provide more immediate fitness benefits to parasites, such that selection may favour evolution toward a generalist strategy. Here, we test for directionality in the evolution of host specificity using a large data set and phylogenetic information on 297 species of fleas parasitic on small mammals. The analyses determined whether host specificity, measured both as the number of host species exploited and their taxonomic diversity, was related to clade rank of the flea species, or the number of branching events between an extant species and the root of the phylogenetic tree (i.e., the total path length from the root of the tree to the species). Based on regression analyses, we found positive relationships between the number of host species used and clade rank across all 297 species, as well as within one (Hystrichopsyllidae) of four large families and one of seven large genera investigated separately; in addition, we found a positive relationship between the taxonomic diversity of host species used and clade rank in another of the seven genera. These results suggest a slight evolutionary trend of decreasing host specificity. Using a much more conservative likelihood ratio test, however, a random walk, or null model, of evolution could not be discarded in favour of the directional trends in all cases mentioned above. Still, these results suggest that host specificity may have tended to decrease in many flea lineages, a process that could have been driven by the benefits of exploiting a wide range of host species.