Melanin- and carotenoid-based ornaments often signal different aspects of individual quality or similar aspects under different environmental conditions and, thus, they may become evolutionarily integrated into a composite sexual trait. On the other hand, functionally and developmentally different characters (e.g. coloration characters of different developmental origin) are more likely to evolve independently from each other than more similar traits. Here, we examined evolutionary correlations between the occurrence of a conspicuous melanin-based ornament (hood) and carotenoid-based bare-part ornaments within gull family. We also aimed to identify major ecological, life-history, and biogeographical predictors of hood occurrence and reconstruct evolutionary history of this ornament. We found that hood occurrence was associated with red or dark coloration of unfeathered traits (bill and legs), while combinations of hood with yellow carotenoid-based coloration of integument were evolutionarily avoided. Also, hood occurrence correlated negatively with the occurrence of other melanin-based plumage character (mantle). Breeding latitude and habitat were identified as major predictors of hood occurrence in gulls, as hoods were recorded more frequently in low-latitude and inland (rather than marine) species. Finally, our analysis provided support for evolutionary lability in hood occurrence, with a dominance of transitions towards hood loss in the evolutionary history of gulls. The results of our study provide one of the first evidence for a correlated evolution of melanin- and carotenoid-based ornaments in an avian lineage, which supports evolutionary modularity of developmentally and functionally different coloration traits.