Integumentary patterns and colors can differentiate species, sexes, and life changes and can inform on habitat and ecology. However, they are rarely preserved in the fossil record. Here, we report on an extremely well-preserved specimen of the Cretaceous bird Confuciusornis with unprecedented complexity, including small spots on the wings, crest, and throat. Morphological and chemical evidence suggest that these patterns are produced by melanin, but unusual preservation prevents assignment of specific colors. Based on comparisons with extant birds, these patterns were likely used for camouflage, although other functions including sexual signaling cannot be ruled out. Our data show that even more elaborate plumage patterns than the spangles in Anchiornis and stripes in Sinosauropteryx were present at a relatively early stage of avian evolution, showing the significance of coloration and patterning to feather evolution.