Avian plumage colors are frequently used in studies of sexual selection, yet surprisingly little is known about how these traits evolve under different mating systems. We compared historical rates of divergence in male color patterns among the oropendolas and caciques (genera Cacicus, Gymnostinops, Ocyalus, and Psarocolius), a group with both polygynous and monogamous representatives. Reconstructing the evolution of individual color patches on a molecular phylogeny showed that overall color patterns have changed much more rapidly in oropendolas, which comprise two groups that evolved polygyny independently, than in caciques, which are predominantly monogamous. None of these taxa are notably sexually dichromatic, however, suggesting that higher rates of plumage evolution occurred in both sexes rather than just males. Despite high rates of change, color patterns show few examples of convergence among taxa, similar to the lack of homoplasy in male song among oropendolas but in a stark contrast to the repeated convergence in both plumage and song patterns found in a closely related, monogamous clade, the New World orioles (Icterus). Our results support previous suggestions that display traits evolve more rapidly and with less homoplasy in polygynous mating systems, and we provide surprising evidence that these patterns may occur in both sexes.