Bark beetles are feared as pests in forestry but they also support a large number of other taxa that exploit the beetles and their galleries. Among arthropods, mites are the largest taxon associated with bark beetles. Many of these mites are phoretic and often involved in complex interactions with the beetles and other organisms. Within the oribatid mite family Scheloribatidae, only two of the three nominal species of Paraleius have been frequently found in galleries of bark beetles and on the beetles themselves. One of the species, P. leontonychus, has a wide distribution range spanning over three ecozones of the world and is believed to be a host generalist, reported from numerous bark beetle and tree species. In the present study, phylogenetic analyses of one mitochondrial and two nuclear genes identified six well supported, fairly divergent clades within P. leontonychus which we consider to represent distinct species based on molecular species delimitation methods and largely congruent clustering in mitochondrial and nuclear gene trees. These species do not tend to be strictly host specific and might occur syntopically. Moreover, mito-nuclear discordance indicates a case of past hybridization/introgression among distinct Paraleius species, the first case of interspecific hybridization reported in mites other than ticks.