A wide range of organisms use sex pheromones to communicate with each other and to identify appropriate mating partners. While the evolution of chemical communication has been suggested to cause sexual isolation and speciation, the mechanisms that govern evolutionary transitions in sex pheromone production are poorly understood. Here, we decipher the molecular mechanisms underlying the rapid evolution in the expression of a gene involved in sex pheromone production in Drosophilid flies. Long-chain cuticular hydrocarbons (e.g., dienes) are produced female-specifically, notably via the activity of the desaturase DESAT-F, and are potent pheromones for male courtship behavior in Drosophila melanogaster. We show that across the genus Drosophila, the expression of this enzyme is correlated with long-chain diene production and has undergone an extraordinary number of evolutionary transitions, including six independent gene inactivations, three losses of expression without gene loss, and two transitions in sex-specificity. Furthermore, we show that evolutionary transitions from monomorphism to dimorphism (and its reversion) in desatF expression involved the gain (and the inactivation) of a binding-site for the sex-determination transcription factor, DOUBLESEX. In addition, we documented a surprising example of the gain of particular cis-regulatory motifs of the desatF locus via a set of small deletions. Together, our results suggest that frequent changes in the expression of pheromone-producing enzymes underlie evolutionary transitions in chemical communication, and reflect changing regimes of sexual selection, which may have contributed to speciation among Drosophila.