Aposematic signals represent one of the classical systems to study evolution and, as such, they have received considerable empirical and theoretical investigation. Despite the extensive literature on aposematic coloration, much uncertainty remains about genetic changes responsible for the repeated evolution of similar signals in multiple lineages. Here, we study the diversification and convergence of coloration among lineages of aposematic harlequin poison frogs (O. histrionica complex). Our results suggest that different background phenotypes, showing different color and/or luminance contrast, have evolved independently at least twice in this group. We suggest that cellular arrangements are behind the striking diversity of color and patterns in this group and propose that differences in dorsal background color may be related to either or both, the presence/absence of xanthophores and the dispersion of melanosomes. Our genetic analyses support a role for the melanocortin receptor MC1R in melanosome aggregation, and we show evidence that two different mutations (∆433 and C432A) are responsible for the darker phenotypes that may display a more detectable, easier to learn, aposematic signal.