The cichlid fishes of Lake Malawi represent one of the most diverse adaptive radiations of vertebrates known. Among the rock-dwelling cichlids (mbuna), closely related sympatric congeners possess similar trophic morphologies (i.e. cranial and jaw structures), defend overlapping or adjacent territories, but can be easily distinguished based on male nuptial coloration. The apparent morphological similarity of congeners, however, leads to an ecological conundrum: theory predicts that ecological competition should lead to competitive exclusion. Hence, we hypothesized that slight, yet significant, ecological differences accompanied the divergence in sexual signals and that the divergence of ecological and sexual traits is correlated. To evaluate this hypothesis, we quantified body shape, a trait of known ecological importance, in populations of Maylandia zebra, a barred, widespread mbuna, and several sympatric non-barred congeners. We found that the barred populations differ in body shape from their non-barred sympatric congeners and that the direction of shape differences was consistent across all barred versus non-barred comparisons. Barred species are generally deeper-bodied which may be an adaptation to the structurally complex habitat they prefer, whereas the non-barred species have a more fusiform body shape, which may be adaptive in their more open micro-habitat. Furthermore, M. zebra populations sympatric with non-barred congeners differ from populations where the non-barred phenotype is absent and occupy less morphospace, indicating potential ecological character displacement. Mitochondrial DNA as well as published AFLP data indicated that the non-barred populations are not monophyletic and therefore may have evolved multiple times independently. Overall our data indicate that the evolution of coloration and body shape may be coupled as a result of correlational selection. We hypothesize that correlated evolution of sexually selected and ecological traits may have contributed to rapid speciation as well as the maintenance of diversity in one of the most diverse adaptive radiations known.