We studied patterns of variation in species composition of flea assemblages on small mammals across different habitats of Slovakia and compared flea species composition within and across host species among habitats. We asked (1) how variable the composition of flea assemblages is among different populations of the same host occurring in different habitats and (2) whether the composition of flea assemblages in a habitat is affected either by species composition of hosts or by environmental affinities of this habitat. Between-habitat similarity in flea species composition increased with an increase in the similarity in host species composition. Species richness of flea assemblages of a host species correlated positively with mean number of cohabitating host species but not with the number of habitats occupied by a host species. Results of the ordination of flea collections from each individual host demonstrated that the first five principal components explained most of the variance in species composition of flea assemblages. The segregation between rodent and insectivore flea assemblages was easily discerned from the ordination diagram when flea assemblages were plotted according to their hosts. When flea assemblages were plotted according to their habitat affinities, the distinction of habitats based on variation in flea composition was not as clear. The results of ANOVA of each principal component showed the significant effect of both host species and habitat type. The variation in each principal component was explained better by the factor of host species compared with the factor of habitat type. Multidimensional scaling of flea assemblages within host species across habitats demonstrated that among-habitat variation in flea composition was manifested differently in different hosts.