Many species have elaborate and complex coloration and patterning, which often differ between the sexes. Sexual selection may increase the size or intensity of color patches (elaboration) in one sex or drive the evolution of novel signal elements (innovation). The latter potentially increases color pattern complexity. Color pattern complexity may also be influenced by ecological factors related to predation and environment; however, very few studies have investigated the effects of both sexual and natural selection on color pattern complexity across species. We used a phylogenetic comparative approach to examine these effects in 85 species and subspecies of Australian dragon lizards (family Agamidae). We quantified color pattern complexity by adapting the Shannon–Wiener diversity index. There were clear sex differences in color pattern complexity, which were positively correlated with both sexual dichromatism and sexual size dimorphism, consistent with the idea that sexual selection plays a significant role in the evolution of color pattern complexity. By contrast, we found little evidence of a link between environmental factors and color pattern complexity on body regions exposed to predators. Our results suggest that sexual selection rather than natural selection has led to increased color pattern complexity in males.