The independent evolution of similar traits across multiple taxa provides some of the most compelling evidence of natural selection. Little is known, however, about the genetic basis of these convergent or parallel traits: are they mediated by identical or different mutations in the same genes, or unique mutations in different genes? Using a combination of candidate gene and reduced representation genomic sequencing approaches, we explore the genetic basis of and the evolutionary processes that mediate similar plumage colour shared by isolated populations of the Monarcha castaneiventris flycatcher of the Solomon Islands. A genome-wide association study (GWAS) that explicitly controlled for population structure revealed that mutations in known pigmentation genes are the best predictors of parallel plumage colour. That is, entirely black or melanic birds from one small island share an amino acid substitution in the melanocortin-1 receptor (MC1R), whereas similarly melanic birds from another small island over 100 km away share an amino acid substitution in a predicted binding site of agouti signalling protein (ASIP). A third larger island, which separates the two melanic populations, is inhabited by birds with chestnut bellies that lack the melanic MC1R and ASIP allelic variants. Formal FST outlier tests corroborated the results of the GWAS and suggested that strong, directional selection drives the near fixation of the MC1R and ASIP variants across islands. Our results, therefore, suggest that selection acting on different mutations with large phenotypic effects can drive the evolution of parallel melanism, despite the relatively small population size on islands.