Socio-sexual environments have profound effects on fitness. Local sex ratios can alter the threat of sexual competition, to which males respond via plasticity in reproductive behaviors and ejaculate composition. In Drosophila melanogaster, males detect the presence of conspecific, same-sex mating rivals prior to mating using multiple, redundant sensory cues. Males that respond to rivals gain significant fitness benefits by altering mating duration and ejaculate composition. Here we investigated the underlying genome-wide changes involved. We used RNA-seq to analyze male transcriptomic responses 2, 26, and 50 h after exposure to rivals, a time period that was previously identified as encompassing the major facets of male responses to rivals. The results showed a strong early activation of multiple sensory genes in the head-thorax (HT), prior to the expression of any phenotypic differences. This gene expression response was reduced by 26 h, at the time of maximum phenotypic change, and shut off by 50 h. In the abdomen (A), fewer genes changed in expression and gene expression responses appeared to increase over time. The results also suggested that different sets of functionally equivalent genes might be activated in different replicates. This could represent a mechanism by which robustness is conferred upon highly plastic traits. Overall, our study reveals that mRNA-seq can identify subtle genomic signatures characteristic of flexible behavioral phenotypes.