Genes of major phenotypic effects and strong genetic correlations can facilitate adaptation, direct selective responses, and potentially lead to phenotypic convergence. However, the preponderance of this type of genetic architecture in repeatedly evolved adaptations remains unknown. Using hybrids between Haplochromis chilotes (thick-lipped) and Pundamilia nyererei (thin-lipped) we investigated the genetics underlying hypertrophied lips and elongated heads, traits that evolved repeatedly in cichlids. At least 25 loci of small-to-moderate and mainly additive effects were detected. Phenotypic variation in lip and head morphology was largely independent. Although several QTL overlapped for lip and head morphology traits, they were often of opposite effects. The distribution of effect signs suggests strong selection on lips. The fitness implications of several detected loci were demonstrated using a laboratory assay testing for the association between genotype and variation in foraging performance. The persistence of low fitness alleles in head morphology appears to be maintained through antagonistic pleiotropy/close linkage with positive-effect lip morphology alleles. Rather than being based on few major loci with strong positive genetic correlations, our results indicate that the evolution of the Lake Victoria thick-lipped ecomorph is the result of selection on numerous loci distributed throughout the genome.