The presence of genetic variation for learning ability in animals opens the way for experiments asking how and under what ecological circumstances improved learning ability should evolve. Here we report experimental evolution of learning ability in Drosophila melanogaster. We exposed experimental populations for 51 generations to conditions that we expected to favor associative learning with regard to oviposition substrate choice. Flies that learned to associate a chemical cue (quinine) with a particular substrate, and still avoided this substrate several hours after the cue had been removed, were expected to contribute more alleles to the next generation. From about generation 15 on, the experimental populations showed marked ability to avoid oviposition substrates that several hours earlier had contained the chemical cue. The improved response to conditioning was also expressed when the flies were faced with a choice of novel media. We demonstrate that these behavioral changes are caused by the evolution of both a higher learning rate and a better memory.