Sexual signaling is an important reproductive barrier known to evolve early during the formation of new species, but the genetic mechanisms that facilitate the divergence of sexual signals remain elusive. Here we isolate a gene linked to the rapid evolution of a signaling trait in a pair of nascent neotropical orchid bee lineages, Euglossa dilemma and E. viridissima. Male orchid bees acquire chemical compounds from their environment to concoct species-specific perfumes to later expose during courtship. We find that the two lineages acquire chemically distinct perfumes and are reproductively isolated despite low levels of genome-wide differentiation. Remarkably, variation in perfume chemistry coincides with rapid divergence in few odorant receptor (OR) genes. Using functional assays, we demonstrate that the derived variant of Or41 in E. dilemma is specific towards its species-specific major perfume compound, whereas the ancestral variant in E. viridissima is broadly tuned to multiple odorants. Our results show that OR evolution likely played a role in the divergence of sexual communication in natural populations.