This study builds upon an earlier experiment that examined the dynamics of mean fitness in evolving populations of Escherichia coli in which mutations were the sole source of genetic variation. During thousands of generations in a constant environment, the rate of improvement in mean fitness of these asexual populations slowed considerably from an initially rapid pace. In this study, we sought to determine whether sexual recombination with novel genotypes would reaccelerate the rate of adaption in these populations. To that end, treatment populations were propagated for an additional 1000 generations in the same environment as their ancestors, but they were periodically allowed to mate with an immigrant pool of genetically distinct Hfr (high frequency recombination) donors. These donors could transfer genes to the resident populations by conjugation, but the donors themselves could not grow in the experimental environment. Control populations were propagated under identical conditions, but in the absence of sexual recombination with the donors. All twelve control populations retained the ancestral alleles at every locus that was scored. In contrast, the sexual recombination treatment yielded dramatic increases in genetic variation. Thus, there was a profound effect of recombination on the rate of genetic change. However, the increased genetic variation in the treatment populations had no significant effect on the rate of adaptive evolution, as measured by changes in mean fitness relative to a common competitor. We then considered three hypotheses that might reconcile these two outcomes: recombination pressure, hitchhiking of recombinant genotypes in association with beneficial mutations, and complex selection dynamics whereby certain genotypes may have a selective advantage only within a particular milieu of competitors. The estimated recombination rate was too low to explain the observed rate of genetic change, either alone or in combination with hitchhiking effects. However, we documented complex ecological interactions among some recombinant genotypes, suggesting that our method for estimating fitness relative to a common competitor might have underestimated the rate of adaptive evolution in the treatment populations.