The concept of evolvability is controversial. To some, it is simply a measure of the standing genetic variation in a population and can be captured by the narrow-sense heritability (h2). To others, evolvability refers to the capacity to generate heritable phenotypic variation. Many scientists, including Darwin, have argued that environmental variation can generate heritable phenotypic variation. However, their theories have been difficult to test. Recent theory on the evolution of sex and recombination provides a much simpler framework for evaluating evolvability. It shows that modifiers of recombination can increase in prevalence whenever low fitness individuals produce proportionately more recombinant offspring. Because recombination can generate heritable variation, stress-induced recombination might be a plausible mechanism of evolvability if populations exhibit a negative relationship between fitness and recombination. Here we use the fruit fly, Drosophila melanogaster, to test for this relationship. We exposed females to mating stress, heat shock or cold shock and measured the temporary changes that occurred in reproductive output and the rate of chromosomal recombination. We found that each stress treatment increased the rate of recombination and that heat shock, but not mating stress or cold shock, generated a negative relationship between reproductive output and recombination rate. The negative relationship was absent in the low-stress controls, which suggests that fitness and recombination may only be associated under stressful conditions. Taken together, these findings suggest that stress-induced recombination might be a mechanism of evolvability.