Learning through trial-and-error interactions allows animals to adapt innate behavioural ‘rules of thumb’ to the local environment, improving their prospects for survival and reproduction. Naive Drosophila melanogaster males, for example, court both virgin and mated females, but learn through experience to selectively suppress futile courtship towards females that have already mated. Here we show that courtship learning reflects an enhanced response to the male pheromone cis-vaccenyl acetate (cVA), which is deposited on females during mating and thus distinguishes mated females from virgins. Dissociation experiments suggest a simple learning rule in which unsuccessful courtship enhances sensitivity to cVA. The learning experience can be mimicked by artificial activation of dopaminergic neurons, and we identify a specific class of dopaminergic neuron that is critical for courtship learning. These neurons provide input to the mushroom body (MB) γ lobe, and the DopR1 dopamine receptor is required in MBγ neurons for both natural and artificial courtship learning. Our work thus reveals critical behavioural, cellular and molecular components of the learning rule by which Drosophila adjusts its innate mating strategy according to experience.