The traits involved in sexual selection, such as male secondary sexual characteristics and female mate choice, often co-evolve which can promote population differentiation. However, the genetic architecture of these phenotypes can influence their evolvability and thereby affect the divergence of species. The extraordinary diversity of East African cichlid fishes is often attributed to strong sexual selection and thus this system provides an excellent model to test predictions regarding the genetic architecture of sexually selected traits that contribute to reproductive isolation. In particular, theory predicts that rapid speciation is facilitated when male sexual traits and female mating preferences are controlled by a limited number of linked genes. However, few studies have examined the genetic basis of male secondary sexual traits and female mating preferences in cichlids and none have investigated the genetic architecture of both jointly. In this study, we artificially hybridized a pair of behaviorally isolated cichlid fishes from Lake Malawi and quantified both melanistic color pattern and female mate choice. We investigated the genetic architecture of both phenotypes using quantitative genetic analyses. Our results suggest that 1) many non-additively acting genetic factors influence melanistic color patterns, 2) female mate choice may be controlled by a minimum of 1–2 non-additive genetic factors, and 3) F2 female mate choice is not influenced by male courting effort. Furthermore, a joint analysis of color pattern and female mate choice indicates that the genes underlying these two traits are unlikely to be physically linked. These results suggest that reproductive isolation may evolve rapidly owing to the few genetic factors underlying female mate choice. Hence, female mate choice likely played an important role in the unparalleled speciation of East African cichlid fish.