Why females of many species mate multiply in the absence of direct benefits remains an open question in evolutionary ecology. Interacting and mating with multiple males can be costly to females in terms of time, resources, predation risk, and disease transmission. A number of indirect genetic benefits have been proposed to explain such behaviors, but the relative importance of these mechanisms in natural systems remains unclear. We tested for several direct and indirect benefits of polyandry in the walking stick Timema cristinae. We found no evidence of direct benefits with respect to longevity or fecundity. However, male x female genotypic interactions affected egg-hatching success and offspring production independent of relatedness, suggesting that mating with certain males benefits females and that the best male may differ for each female. Furthermore, multiply mated females biased paternity toward one or few males, and the extent of this bias was positively correlated to egg-hatching success. Our data, therefore, provide evidence for indirect benefits through compatibility effects in this species. By mating multiply, females may improve their chances of mating with a compatible male if compatibility cannot be assessed before mating. Such compatibility effects can explain the evolution and maintenance of polyandry in Timema and many other species.