Hox genes have been implicated in the evolution of many animal body patterns, but the molecular events underlying trait modification have not been elucidated. Pigmentation of the posterior male abdomen is a recently acquired trait in the Drosophila melanogaster lineage. Here, we show that the Abdominal-B (ABD-B) Hox protein directly activates expression of the yellow pigmentation gene in posterior segments. ABD-B regulation of pigmentation evolved through the gain of ABD-B binding sites in a specific cis-regulatory element of the yellow gene of a common ancestor of sexually dimorphic species. Within the melanogaster species group, male-specific pigmentation has subsequently been lost by at least three different mechanisms, including the mutational inactivation of a key ABD-B binding site in one lineage. These results demonstrate how Hox regulation of traits and target genes is gained and lost at the species level and have general implications for the evolution of body form at higher taxonomic levels.