Polyandry, i.e. females mating with multiple males, is more common than previously anticipated and potentially provides both direct and indirect fitness benefits to females. The level of polyandry (defined by the lifetime number of male mates of a female) is an important determinant of the occurrence and intensity of sexual selection acting on male phenotypes. While the forces of sexual selection acting on phenotypic male traits such as body size are relatively well understood, sexual selection acting on phenotypic plasticity of these traits is unexplored. We tackled this issue by scrutinizing the link between polyandry and phenotypic plasticity of male body size in two sympatric plant-inhabiting predatory mite species, Phytoseiulus persimilis and Neoseiulus californicus. These two species are similar in life history, ecological niche requirements, mating behavior, polygyny and female body size plasticity but strikingly differ in the level of both polyandry and phenotypic plasticity of male body size (both lower in P. persimilis). We hypothesized that deviations from standard body size, i.e. the size achieved under favorable conditions, incur higher costs for males in the less polyandrous P. persimilis. To test our hypotheses, we conducted two experiments on (i) the effects of male body size on spermatophore transfer in singly mating females and (ii) the effects of mate sequence (switching the order of standard-sized and small males) on mating behavior and paternity success in doubly mating females. In P. persimilis but not N. californicus, small males transferred fewer but larger spermatophores to the females; in both species, females re-mated more likely with standard-sized following small than small following standard-sized males; in P. persimilis, first standard-sized males sired a higher proportion of offspring produced after re-mating by the female than first small males, whereas in N. californicus the paternity success of small and standard-sized males was independent of the mating sequence. Based on our results and pertinent previous studies, which showed that females of P. persimilis, but not N. californicus, prefer mating with standard-sized over small males and allow them fertilizing more eggs, the lack of interspecific difference in female body size plasticity, and the absence of any clue pointing at a role of natural selection, we suggest that the interspecific difference in male body size plasticity is sexually selected. Our study provides an indication of sexual selection constraining plasticity of male phenotypes, suggesting that the level of polyandry may be an important co-determinant of the level of phenotypic plasticity of male body size.