The most basic models of learning are reinforcement learning models (for instance, classical and operant conditioning) that posit a constant learning rate; however many animals change their learning rates with experience. This process is sometimes studied by reversing an existing association between cues and rewards, and measuring the rate of relearning. Augmented reversal-learning, where learning rates increase with practice, can be an important component of behavioral flexibility; and may provide insight into higher cognition. Previous studies of reversal-learning in Drosophila have not measured learning rates, but have tended to focus on measuring gross deficits in reversal-learning, as the ratio of two timepoints. These studies have uncovered a diversity of mechanisms underlying reversal-learning, but natural genetic variation in this trait has yet to be assessed. We conducted a reversal-learning regime on a diverse panel of Drosophila melanogaster genotypes. We found highly significant genetic variation in their baseline ability to learn. We also found that they have a consistent, and strong (1.3×), increase in their learning speed with reversal. We found no evidence, however, that there was genetic variation in their ability to increase their learning rates with experience. This may suggest that Drosophila have a hitherto unrecognized ability to integrate acquired information, and improve their decision making; but that their mechanisms for doing so are under strong constraints.