Polyandry is more widespread than anticipated from Bateman's principle but its ultimate (evolutionary) causes and proximate (mechanistic) correlates are more difficult to pinpoint than those of polygyny. Here, we combined mating experiments, quantification of reproductive traits and microsatellite genotyping to determine the fitness implications of polyandry in two predatory mite species, where males are highly polygynous (up to 45 fertilized females during life), whereas females range from monandry to various polyandry levels. The medium-level polyandrous (up to eight male mates possible) Neoseiulus californicus received clear direct and indirect benefits: multiply mated females produced more offspring with higher survival chances over longer times than singly mated females. In contrast, singly and multiply mated females of the low-level polyandrous (commonly two male mates at maximum) Phytoseiulus persimilis produced similar numbers of offspring having similar survival chances. In both species, multiple mating resulted in mixed offspring paternities, opening the chance for indirect fitness benefits such as enhanced genetic compatibility, complementarity and/or variability. However, the female re-mating likelihood and the paternity chance of non-first male mates were lower in P. persimilis than in N. californicus. Regarding proximate factors, in both species first mating duration and female re-mating likelihood were negatively correlated. Based on occasional fertilization failure of first male mates in P. persimilis, and mixed offspring paternities in both species, we argue that fertilization assurance and the chance to gain indirect fitness benefits are the ultimate drivers of polyandry in P. persimilis, whereas those of N. californicus are higher offspring numbers coupled with enhanced offspring viability and possibly other indirect fitness benefits. Overall, the adaptive significance and proximate events well reflected the polyandry levels. Our study provides a key example for linking behavioral experiments, quantification of reproductive traits and paternity analysis via offspring genotyping to explain the evolution of differing levels of polyandry.