Whether general patterns of signal evolution can be explained by selection for signal efficacy (detectability) has yet to be established. To establish the importance of signal efficacy requires evidence that both signals and their detectability to receivers have evolved in response to habitat shifts in a predictable fashion. Here, we test whether habitat structure has predictable effects on the evolution of male and female display coloration in 21 lineages of African dwarf chameleon (Bradypodion), based on a phylogenetic comparative analysis. We used quantitative measures of display coloration and estimated signal detectability as the contrast of those colors among body regions or against the background vegetation as perceived by the chameleon visual system. Both male and female display colors varied predictably with different aspects of habitat structure. In several (but not all) instances, habitat-associated shifts in display coloration resulted in habitat-associated variation in detectability. While males exhibit a remarkable variety of colors and patterns, female display coloration is highly conserved, consisting in all populations of contrasting dark and light elements. This color pattern may maximize detectability across all habitat types, potentially explaining female conservatism. Overall, our results support the view that selection for signal efficacy plays an important role in the evolution of animal signals.