1. We studied temporal variation in the structure of flea communities on small mammalian hosts from eastern Slovakia using null models. We asked (a) whether flea co-occurrences in infracommunities (in the individual hosts) in different hosts as well as in the component communities (in the host species) demonstrate a non-random pattern; (b) whether this pattern is indicative of either positive or negative flea species interactions; (c) whether this pattern varies temporally; and (d) whether the expression of this pattern is related to population size of either fleas or hosts or both. 2. We constructed a presence/absence matrix of flea species for each temporal sample of a host species and calculated four metrics of co-occurrence, namely the C-score, the number of checkerboard species pairs, the number of species combinations and the variance ratio (V-ratio). Then we compared these metrics with the respective indices calculated for 5000 null matrices that were assembled randomly using two algorithms, namely fixed-fixed (FF) and fixed-equiprobable (FE). 3. Most co-occurrence metrics calculated for real data did not differ significantly from the metrics calculated for simulated matrices using the FF algorithm. However, the indices observed for 42 of 75 presence/absence matrices differed significantly from the null expectations for the FE models. Non-randomness was detected mainly by the C-score and V-ratio metrics. In all cases, the direction of non-randomness was the same, namely the aggregation, not competition, of flea species in host individuals and host species. 4. The inclusion or exclusion of the uninfested hosts in the FE models did not affect the results for individual host species. However, exclusion of the uninfested host species led to the acceptance of the null hypothesis for only six of 13 temporal samples of the component flea communities for which non-randomness was detected when the uninfested hosts were included in the analysis. 5. In most host species, the absolute values of the standardized size effect of both the C-score and V-ratio increased with an increase in host density and a concomitant decrease in flea abundance and prevalence. 6. Results of this study demonstrated that (a) flea assemblages on small mammalian hosts were structured at some times, whereas they appeared to be randomly assembled at other times; (b) whenever non-randomness of flea co-occurrences was detected, it suggested aggregation but never segregation of flea species in host individuals or populations; and (c) the expression of structure in flea assemblages depended on the level of density of both fleas and hosts.