Infertility is common in nature despite its obvious cost to individual fitness. Rising global temperatures are predicted to decrease fertility, and male sterility is frequently used in attempts to regulate pest or disease vector populations. When males are infertile, females may mate with multiple males to ensure fertilisation, and changes in female mating behaviour in turn could intensify selection on male fertility. Fertility assurance is a potentially wide-spread explanation for polyandry, but whether and how it actually contributes to the evolution of polyandry is not clear. Moreover, whether a drop in male fertility would lead to a genetic increase in polyandry depends on whether females respond genetically or through behavioural plasticity to male infertility. Here, we experimentally manipulate male fertility through heat-exposure in Drosophila pseudoobscura, and test female discrimination against infertile males before and after mating. Using isogenic lines, we compare the roles of behaviourally plastic versus genetically fixed polyandry. We find that heat-exposed males are less active and attractive, and that females are more likely to remate after mating with these males. Remating rate increases with reduced reproductive output, indicating that females use current sperm storage threshold to make dynamic remating decisions. After remating with fertile males, females restore normal fecundity levels. Our results suggest that male infertility could explain the evolution of adaptively flexible polyandry, but is less likely to cause an increase in genetic polyandry.