The maintenance of sexual reproduction in natural populations is a pressing question for evolutionary biologists [1, 2]. Under the "Red Queen" hypothesis, coevolving parasites reduce the reproductive advantage of asexual reproduction by adapting to infect clonal genotypes after they become locally common [3–6]. In addition, the "geographic mosaic" theory of coevolution proposes that structured populations of interacting species can produce selection mosaics manifested as coevolutionary "hot spots" and "cold spots" [7]. Here, we tested whether a steep, habitat-specific cline in the frequency of sexual reproduction in a freshwater snail could be explained by the existence of hot spots and cold spots for coevolving parasites. We found that the shallow-water margins of lakes, where sexual reproduction is most common, are coevolutionary hot spots, and that deeper habitats are cold spots. These results are consistent with the geographic mosaic theory, in that the intensity of selection resulting from biological interactions can vary sharply in space. The results also support the Red Queen hypothesis, in that sex is associated with coevolutionary hot spots for virulent parasites.