Sleep is a highly conserved behavior, yet its duration and pattern vary extensively among species and between individuals within species. The genetic basis of natural variation in sleep remains unknown.We used the Drosophila Genetic Reference Panel (DGRP) to perform a genome-wide association (GWA) study of sleep in D. melanogaster. We identified candidate single nucleotide polymorphisms (SNPs) associated with differences in the mean as well as the environmental sensitivity of sleep traits; these SNPs typically had sex-specific or sex-biased effects, and were generally located in non-coding regions. The majority of SNPs (80.3%) affecting sleep were at low frequency and had moderately large effects. Additive models incorporating multiple SNPs explained as much as 55% of the genetic variance for sleep in males and females. Many of these loci are known to interact physically and/or genetically, enabling us to place them in candidate genetic networks. We confirmed the role of seven novel loci on sleep using insertional mutagenesis and RNA interference.We identified many SNPs in novel loci that are potentially associated with natural variation in sleep, as well as SNPs within genes previously known to affect Drosophila sleep. Several of the candidate genes have human homologues that were identified in studies of human sleep, suggesting that genes affecting variation in sleep are conserved across species. Our discovery of genetic variants that influence environmental sensitivity to sleep may have a wider application to all GWA studies, because individuals with highly plastic genotypes will not have consistent phenotypes.