One of the most intriguing features of animal development and evolution is the rapid turnover of sex-specific traits. Most animal species are sexually dimorphic, yet the characters distinguishing males from females are different in every case. This simple observation implies that new sexual characters are gained, and old ones are lost, during the evolution of every animal lineage. The molecular mechanisms of this turnover are poorly understood. We are using the “sex comb” of Drosophila, a recently evolved and rapidly diversifying male-specific structure, to elucidate how new sexually dimorphic traits originate and evolve. Key roles in this process are played by the HOX gene Sex combs reduced (Scr) and by the doublesex (dsx) transcription factor, the main effector of the Drosophila sex determination pathway. Only some cells in Drosophila express dsx, resulting in a complex mosaic of “sex-aware” and “sex-naive” cells. In D. melanogaster, which has sex combs, dsx expression in the presumptive sex comb region is activated by Scr, and the male-specific isoform of dsx up-regulates Scr so that both genes become expressed at high levels in this region in males but not in females. Precise spatial regulation of both dsx and Scr is essential for defining sex comb position and structure. Comparative analysis of Scr and dsx expression reveals a tight correlation between sex comb size, position, and morphology and the expression patterns of both genes. In Drosophila species that primitively lack sex combs, no dsx expression is observed in the homologous region while Scr shows no male-specific upregulation, suggesting that the origin and diversification of sex combs were linked to the gain of a new, Scr-dependent expression domain of dsx, and to the evolution of the Scr/dsx autoregulatory loop. At the molecular level, these changes were caused by the origin of a new cis-regulatory element that drives dsx expression in the sex comb, and by changes in the spatial activity of Scr enhancers. Two other, distantly related fly lineages that independently evolved novel male-specific structures show convergent evolutionary gains of dsx expression in the corresponding tissues. Thus, changes in the spatial regulation of sex-determining genes may be a key mechanism that enables the evolution of new sex-specific traits, contributing to some of the most dramatic examples of phenotypic diversification in nature.