Melanins are widespread pigments in vertebrates, with important roles in visual signaling, UV protection, and homeostasis. Fossil evidence of melanin and melanin-bearing organelles - melanosomes - in ancient vertebrates may illuminate the evolution of melanin and its functions, but macroevolutionary trends are poorly resolved. Here, we integrate fossil data with current understanding of melanin function, biochemistry, and genetics. Mapping key genes onto phenotypic attributes of fossil vertebrates identifies potential genomic controls on melanin evolution. Taxonomic trends in the anatomical location, geometry, and chemistry of vertebrate melanosomes are linked to the evolution of endothermy. These shifts in melanin biology suggest fundamental links between melanization and vertebrate ecology. Tissue-specific and taxonomic trends in melanin chemistry support evidence for evolutionary tradeoffs between function and cytotoxicity.