Many insects possess a sexual communication system that is vulnerable to chemical espionage by parasitic wasps. We recently discovered that a hitch-hiking (H) egg parasitoid exploits the antiaphrodisiac pheromone benzyl cyanide (BC) of the Large Cabbage White butterfly Pieris brassicae. This pheromone is passed from male butterflies to females during mating to render them less attractive to conspecific males. When the tiny parasitic wasp Trichogramma brassicae detects the antiaphrodisiac, it rides on a mated female butterfly to a host plant and then parasitizes her freshly laid eggs. The present study demonstrates that a closely related generalist wasp, Trichogramma evanescens, exploits BC in a similar way, but only after learning. Interestingly, the wasp learns to associate an H response to the odors of a mated female P. brassicae butterfly with reinforcement by parasitizing freshly laid butterfly eggs. Behavioral assays, before which we specifically inhibited long-term memory (LTM) formation with a translation inhibitor, reveal that the wasp has formed protein synthesis-dependent LTM at 24 h after learning. To our knowledge, the combination of associatively learning to exploit the sexual communication system of a host and the formation of protein synthesis-dependent LTM after a single learning event has not been documented before. We expect it to be widespread in nature, because it is highly adaptive in many species of egg parasitoids. Our finding of the exploitation of an antiaphrodisiac by multiple species of parasitic wasps suggests its use by Pieris butterflies to be under strong selective pressure.