Why sexual reproduction has evolved to be such a widespread mode of reproduction remains a major question in evolutionary biology. While previous studies have shown that increased sex and recombination can evolve in the presence of host-parasite interactions (the “Red Queen hypothesis” for sex), many of these studies have assumed that multiple loci mediate infection versus resistance. Data suggest, however, that a major locus is typically involved in antigen presentation and recognition. Here, we explore a model where only one locus mediates host-parasite interactions, but a second locus is subject to directional selection. Even though the effects of these genes on fitness are independent, we show that increased rates of sex and recombination are favored at a modifier gene that alters the rate of genetic mixing. This result occurs because of selective interference that occurs in finite populations (the “Hill-Robertson effect”), which also favors sex. These results suggest that the Red Queen hypothesis may help to explain the evolution of sex by contributing a form of persistent selection, which interferes with directional selection at other loci and thereby favors sex and recombination.