The Drosophila fruitless (fru) gene encodes a set of putative transcription factors that promote male sexual behavior by controlling the development of sexually dimorphic neuronal circuitry. However, the mechanism whereby fru establishes the sexual fate of neurons remains enigmatic. Here, we show that Fru forms a complex with the transcriptional cofactor Bonus (Bon), which, in turn, recruits either of two chromatin regulators, Histone deacetylase 1 (HDAC1), which masculinizes individual sexually dimorphic neurons, or Heterochromatin protein 1a (HP1a), which demasculinizes them. Manipulations of HDAC1 or HP1a expression change the proportion of male-typical neurons and female-typical neurons rather than producing neurons with intersexual characteristics, indicating that on a single neuron level, this sexual switch operates in an all-or-none manner.