Males of many species use social cues to predict sperm competition and tailor their reproductive strategies, such as ejaculate or behavioural investment, accordingly. Whilst these plastic strategies are widespread, the underlying mechanisms remain largely unknown. Plastic behaviour requires individuals to learn and memorise cues associated with environmental change before using this experience to modify behaviour. Drosophila melanogaster respond to an increase in sperm competition threat by extending mating duration after exposure to a rival male. This behaviour shows lag times between environmental change and behavioural response suggestive of acquisition and loss of memory. Considering olfaction is important for a male’s ability to assess the sperm competition environment, we hypothesised that an olfactory learning and memory pathway may play a key role in controlling this plastic behaviour. We assessed the role of genes and brain structures known to be involved in learning and memory. We show that sperm competition responses depend on anaesthesia sensitive memory, specifically the genes rut and amn. We also show that the γ lobes of the mushroom bodies are integral to the control of plastic mating behaviour. These results reveal the genetic and neural properties required for reacting to changes in the sperm competition environment.