In order to address the nature of genetic variation in learning performance, we investigated the response to classical olfactory conditioning in "high-learning" Drosophila melanogaster lines previously subject to selection for the ability to learn an association between the flavor of an oviposition medium and bitter taste. In a T-maze choice test, the seven high-learning lines were better at avoiding an odor previously associated with aversive mechanical shock than were five unselected "low-learning" lines originating from the same natural population. Thus, the evolved improvement in learning ability of high-learning lines generalized to another aversion learning task involving a different aversive stimulus (shock instead of bitter taste) and a different behavioral context than that used to impose selection. In this olfactory shock task, the high-learning lines showed improvements in the learning rate as well as in two forms of consolidated memory: anesthesia-resistant memory and long-term memory. Thus, genetic variation underlying the experimental evolution of learning performance in the high-learning lines affected several phases of memory formation in the course of olfactory aversive learning. However, the two forms of consolidated memory were negatively correlated among replicate high-learning lines, which is consistent with a recent hypothesis that these two forms of consolidated memory are antagonistic.