Pigmentation varies within and between species and is often adaptive. The amount of pigmentation on the abdomen of Drosophila melanogaster is a relatively simple morphological trait, which serves as a model for mapping the genetic basis of variation in complex phenotypes. Here, we assessed natural variation in female abdominal pigmentation in 175 sequenced inbred lines of the Drosophila melanogaster Genetic Reference Panel, derived from the Raleigh, NC population. We quantified the proportion of melanization on the two most posterior abdominal segments, tergites 5 and 6 (T5, T6). We found significant genetic variation in the proportion of melanization and high broad-sense heritabilities for each tergite. Genome-wide association studies identified over 150 DNA variants associated with the proportion of melanization on T5 (84), T6 (34), and the difference between T5 and T6 (35). Several of the top variants associated with variation in pigmentation are in tan, ebony, and bric-a-brac1, genes known to affect D. melanogaster abdominal pigmentation. Mutational analyses and targeted RNAi-knockdown showed that 17 out of 28 (61%) novel candidate genes implicated by the genome-wide association study affected abdominal pigmentation. Several of these genes are involved in developmental and regulatory pathways, chitin production, cuticle structure, and vesicle formation and transport. These findings show that genetic variation may affect multiple steps in pathways involved in tergite development and melanization. Variation in these novel candidates may serve as targets for adaptive evolution and sexual selection in D. melanogaster.