The expression in females of ornaments thought to be the target of sexual selection in males is a long-standing puzzle. Two main hypotheses are proposed to account for the existence of conspicuous ornaments in both sexes (mutual ornamentation): genetic correlation between the sexes and sexual selection on females as well as males. We examined the pattern of ornament gains and losses in 240 species of dragon lizards (Agamidae) in order to elucidate the relative contribution of these two factors in the evolution of mutual ornamentation. In addition, we tested whether the type of shelter used by lizards to avoid predators predicts the evolutionary loss or constraint of ornament expression. We found evidence that the origin of female ornaments is broadly consistent with the predictions of the genetic correlation hypothesis. Ornaments appear congruently in both sexes with some lineages subsequently evolving male biased sexual dimorphism, apparently through the process of natural selection for reduced ornamentation in females. Nevertheless, ornaments have also frequently evolved in both sexes independently. This suggests that genetic correlations are potentially weak for several lineages and sexual selection on females is responsible for at least some evolutionary change in this group. Unexpectedly, we found that the evolutionary loss of some ornaments is concentrated more in males than females and this trend cannot be fully explained by our measures of natural selection.