From the brilliant red cardinal to the bright pink flamingo (pictured above), birds can sport a rainbow of colors. These vibrant patterns are due to pigments called carotenoids. Now, researchers have traced the first appearance of these pigments to a theoretical ancestor of perching birds (Passeriformes) that probably lived 56 million years ago, more than 100 million years after brown and black birds owned the skies. The researchers collected and chemically analyzed feathers from nearly 10,000 extant bird species and found that 40% of all bird species’ plumage contains the carotenoid pigment—25% more than previously predicted. After sorting all the birds into carotenoid-present or carotenoid-absent categories, the researchers constructed a family tree to predict the origins of the pigment. The research, published online this week in the Proceedings of the Royal Society B, suggests that birds have become steadily more colorful as time has gone on.