Memory is a complex and dynamic process that is composed of different phases. Its evolution under natural selection probably depends on a balance between fitness benefits and costs. In Drosophila, two separate forms of consolidated memory phases can be generated experimentally: anaesthesia-resistant memory (ARM) and long-term memory (LTM). In recent years, several studies have focused on the differences between these long-lasting memory types and have found that, at the functional level, ARM and LTM are antagonistic. How this functional relationship will affect their evolutionary dynamics remains unknown. We selected for flies with either improved ARM or improved LTM over several generations, and found that flies selected specifically for improvement of one consolidated memory phase show reduced performance in the other memory phase. We also found that improved LTM was linked to decreased longevity in male flies but not in females. Conversely, males with improved ARM had increased longevity. We found no correlation between either improved ARM or LTM and other phenotypic traits. This is, to our knowledge, the first evidence of a symmetrical evolutionary trade-off between two memory phases for the same learning task. Such trade-offs may have an important impact on the evolution of cognitive capacities. On a neural level, these results support the hypothesis that mechanisms underlying these forms of consolidated memory are, to some degree, antagonistic.