Background: The maintenance of considerable genetic variation in sexually selected traits (SSTs) is puzzling given directional selection expected to act on these traits. A possible explanation is the existence of a genotype-by-environment (GxE) interaction for fitness, by which elaborate SSTs are favored in some environments but selected against in others. In the current study, we look for such interactions for fitness-related traits in the bulb mite, a male-dimorphic species with discontinuous expression of a heritable SST in the form of enlarged legs that are used as weapons. Results: We show that evolution at 18°C resulted in populations with a higher prevalence of this SST compared to evolution at 24°C. We further demonstrate that temperature modified male reproductive success in a way that was consistent with these changes. There was a genotype-by-environment interaction for reproductive success - at 18°C the relative reproductive success of armored males competing with unarmored ones was higher than at the moderate temperature of 24°C. However, male morph did not have interactive effects with temperature with respect to other life history traits (development time and longevity). Conclusions: A male genotype that is associated with the expression of a SST interacted with temperature in determining male reproductive success. This interaction caused an elaborate SST to evolve in different directions (more or less prevalent) depending on the thermal environment. The implication of this finding is that seasonal temperature fluctuations have the potential to maintain male polymorphism within populations. Furthermore, spatial heterogeneity in thermal conditions may cause differences among populations in SST selection. This could potentially cause selection against male immigrants from populations in different environments and thus strengthen barriers to gene flow.