Background : Currently many habitats suffer from quality loss due to environmental change. As a consequence, evolutionary trajectories might shift due to environmental effects and potentially increase extinction risk of resident populations. Nevertheless, environmental variation has rarely been incorporated in studies of sexual selection and sexual conflict, although local environments and individuals’ condition undoubtedly influence costs and benefits. Here, we utilise polyandrous and monogamous selection lines of flour beetles, which evolved in presence or absence of sexual selection for 39 generations. We specifically investigated effects of low vs. standard food quality (i.e. stressful vs. benign environments) on reproductive success of cross pairs between beetles from the contrasting female and male selection histories to assess gender effects driving fitness. Results : We found a clear interaction of food quality, male selection history and female selection history. Monogamous females generally performed more poorly than polyandrous counterparts, but reproductive success was shaped by selection history of their mates and environmental quality. When monogamous females were paired with polyandrous males in the standard benign environment, females seemed to incur costs, possibly due to sexual conflict. In contrast, in the novel stressful environment, monogamous females profited from mating with polyandrous males, indicating benefits of sexual selection outweigh costs. Conclusions : Our findings suggest that costs and benefits of sexually selected adaptations in both sexes can be profoundly altered by environmental quality. With regard to understanding possible impacts of environmental change, our results further show that the ecology of mating systems and associated selection pressures should be considered in greater detail.