Melanin is the most widespread pigment in organisms. Melanin-based coloration has been repeatedly observed to be associated with the same traits and in the same direction in different vertebrate and insect species. However, whether any factors that are common to different taxa account for the repeated evolution of melanin-phenotype associations remains unclear. We propose to approach this question from the perspective of convergent and parallel evolution to clarify to what extent different species have evolved the same associations owing to a shared genetic basis and being subjected to similar selective pressures. Our current understanding of the genetic basis of melanin-phenotype associations allows for both convergent and parallel evolution, but this understanding is still limited. Further research is needed to clarify the generality and interdependencies of the different proposed mechanisms (supergenes, pleiotropy based on hormones, or neural crest cells). The general ecological scenarios whereby melanin-based coloration is under selection-protection from ultraviolet radiation, thermoregulation in cold environments, or as a signal of social status-offer a good opportunity to study how melanin-phenotype associations evolve. Reviewing these scenarios shows that some traits associated with melanin-based coloration might be selected together with coloration by also favoring adaptation but that other associated traits might impede adaptation, which may be indicative of genetic constraints. We therefore encourage further research on the relative roles that selection and genetic constraints play in shaping multiple melanin-phenotype associations. Placed into a phylogenetic context, this will help clarify to what extent these associations result from convergent or parallel evolutionary processes and why melanin-phenotype associations are so common across the tree of life.