Polyandry, female mating with multiple males, is widespread across many taxa and almost ubiquitous in insects. This conflicts with the traditional idea that females are constrained by their comparatively large investment in each offspring, and so should only need to mate once or a few times. Females may need to mate multiply to gain sufficient sperm supplies to maintain their fertility, especially in species in which male promiscuity results in division of their ejaculate amongst many females. Here we take a novel approach, utilising wild-caught individuals to explore how natural variation among females and males influences fertility gains for females. We studied this in the Malaysian stalk-eyed fly species Teleopsis dalmanni. After an additional mating, females benefit from greatly increased fertility (proportion fertile eggs). Gains from multiple mating are not uniform across females; they are greatest when females have high fecundity or low fertility. Fertility gains also vary spatially, as we find an additional strong effect of the stream from which females were collected. Responses were unaffected by male mating history (males kept with females or in male-only groups). Recent male mating may be of lesser importance because males in many species, including T. dalmanni, partition their ejaculate to maintain their fertility over many matings. This study highlights the importance of complementing laboratory studies with data on wild-caught populations, where there is considerable heterogeneity between individuals. Future research should focus on environmental, demographic and genetic factors that are likely to significantly influence variation in individual female fecundity and fertility.