Asexual lineages should rapidly replace sexual populations. Why sex then? The Red Queen hypothesis proposes that parasite-mediated selection against common host genotypes could counteract the per-capita birth rate advantage of asexuals. Under the Red Queen, fluctuations in parasite-mediated selection can drive fluctuations in the asexual population, leading to the coexistence of sexual and asexual reproduction. Does shifting selection by parasites drive fluctuations in the fitness and frequency of asexuals in nature? Combining long-term field data with mesocosm experiments, we detected a shift in the direction of parasite selection in the snail Potamopyrgus antipodarum and its coevolving parasite Microphallus sp. In the early 2000's, asexuals were more infected than sexuals. A decade later, the asexuals had declined in frequency and were less infected than sexuals. Over time, the mean infection prevalence of asexuals equaled that of sexuals, but varied far more. This variation in asexual infection prevalence suggests the potential for parasite-mediated fluctuations in asexual fitness. Accordingly, we detected fitness consequences of the shift in parasite selection: when they were less infected than sexuals, asexuals increased in frequency in the field and in paired mesocosms that isolated the effect of parasites. The match between field and experiment argues that coevolving parasites drive temporal change in the relative fitness and frequency of asexuals, potentially promoting the coexistence of reproductive modes in P. antipodarum.