Sex determination mechanisms differ among animal species, but it is not clear how these differences evolve. New sex determiners may arise in response to sexual conflicts, which occur when traits benefit one sex but hinder the other. We identified the genetic basis for the orange-blotch (OB) color pattern, a trait under sexually antagonistic selection in the cichlid fish of Lake Malawi, East Africa. The OB phenotype is due to a cis-regulatory mutation in the Pax7 gene. OB provides benefits of camouflage to females but disrupts the species-specific male color patterns used for mate recognition. We suggest that the resulting sexual conflict over the OB allele has been resolved by selection for a novel female sex determination locus that has invaded populations with an ancestral male sex determination system.