Dramatic pigmentation changes have evolved within most vertebrate groups, including fish and humans. Here we use genetic crosses in sticklebacks to investigate the parallel origin of pigmentation changes in natural populations. High-resolution mapping and expression experiments show that light gills and light ventrums map to a divergent regulatory allele of the Kit ligand (Kitlg) gene. The divergent allele reduces expression in gill and skin tissue and is shared by multiple derived freshwater populations with reduced pigmentation. In humans, Europeans and East Asians also share derived alleles at the KITLG locus. Strong signatures of selection map to regulatory regions surrounding the gene, and admixture mapping shows that the KITLG genomic region has a significant effect on human skin color. These experiments suggest that regulatory changes in Kitlg contribute to natural variation in vertebrate pigmentation, and that similar genetic mechanisms may underlie rapid evolutionary change in fish and humans.