The two sexes of a species can display marked differences in essential behaviors such as feeding or escape from dangers, but the mechanisms underlying such behavioral dimorphism are poorly understood. In our work, we trace the molecular and cellular events that generate sexually dimorphic circuits at the single synapse and gene level. For example, we find that in the circuit for nociceptive behaviors, rewiring of a single synaptic connection can determine the sexually-dimorphic behavioral outcome, while in the tail mechano-sensory circuit different cells and molecular mediators are employed in the two sexes to generate the same behavior. Our work suggests that conflicting evolutionary pressures introduced subtle changes into functional circuits to optimize the fitness of each sex.