The ubiquity of recombination in nature is a paradox because it breaks up combinations of alleles favored by natural selection. Theoretical work has shown that antagonistic coevolution between hosts and parasites can result in rapid fluctuations in epistasis, which can create a short-term advantage to recombination. Here we show that another kind of antagonistic coevolution, inter-locus sexually antagonistic coevolution (SAC), can also create indirect selection for modifiers that increase the rate of recombination, and that it can lead to very high levels of recombination at equilibrium. Recombination is favored because inter-locus SAC creates heterogeneity in the strength and direction of selection, both within and between generations, which maintains an excess of disadvantageous haplotypes in the population. This result is similar to and consistent with dynamics of fluctuating epistasis produced in models of host-parasite coevolution. However, the conditions under which inter-locus SAC provides an advantage to recombination are more permissive.