Sex and recombination are widespread, but explaining these phenomena has been one of the most difficult problems in evolutionary biology. Recombination is advantageous when different individuals in a population carry different advantageous alleles. By bringing together advantageous alleles onto the same chromosome, recombination speeds up the process of adaptation and opposes the fixation of harmful mutations by means of Muller's ratchet. Nevertheless, adaptive substitutions favour sex and recombination only if the rate of adaptive mutation is high, and Muller's ratchet operates only in small or asexual populations. Here, by tracking the fate of modifier alleles that alter the frequency of sex and recombination, we show that background selection against deleterious mutant alleles provides a stochastic advantage to sex and recombination that increases with population size. The advantage arises because, with low levels of recombination, selection at other loci severely reduces the effective population size and genetic variance in fitness at a focal locus (the Hill-Robertson effect), making a population less able to respond to selection and to rid itself of deleterious mutations. Sex and recombination reveal the hidden genetic variance in fitness by combining chromosomes of intermediate fitness to create chromosomes that are relatively free of (or are loaded with) deleterious mutations. This increase in genetic variance within finite populations improves the response to selection and generates a substantial advantage to sex and recombination that is fairly insensitive to the form of epistatic interactions between deleterious alleles. The mechanism supported by our results offers a robust and broadly applicable explanation for the evolutionary advantage of recombination and can explain the spread of costly sex.