Although males and females largely share the same genome and nervous system, they differ profoundly in reproductive investments and require distinct behavioral, morphological, and physiological adaptations. How can the nervous system, while bound by both developmental and biophysical constraints, produce these sex differences in behavior? Here, we uncover a novel dimorphism in Drosophila melanogaster that allows deployment of completely different behavioral repertoires in males and females with minimum changes to circuit architecture. Sexual differentiation of only a small number of higher order neurons in the brain leads to a change in connectivity related to the primary reproductive needs of both sexes-courtship pursuit in males and communal oviposition in females. This study explains how an apparently similar brain generates distinct behavioral repertoires in the two sexes and presents a fundamental principle of neural circuit organization that may be extended to other species.