Most animals depend on olfaction for survival and procreation. Odor-guided behavior is a quantitative trait, with phenotypic variation due to multiple segregating quantitative trait loci (QTL). Despite its profound biological importance, the genetic basis of naturally occurring variation in olfactory behavior remains unexplored. Here, we mapped a single Drosophila QTL affecting variation in avoidance response to benzaldehyde, using a population of recombinant inbred lines. Deficiency complementation mapping resolved this region into one female- and one male-specific QTL. Subsequent quantitative complementation tests to all available mutations of positional candidate genes showed that the female-specific QTL failed to complement a P-element insertional mutation, l(3)04276. The P-element insertion was in the intron of a novel gene, Vanaso, which contains a putative guanylate binding protein domain, is highly polymorphic, and is expressed in the third antennal segment, the major olfactory organ of Drosophila. No expression was detected in the fly brain, suggesting that Vanaso plays a role in peripheral chemosensory processes rather than in central integration of olfactory information. QTL mapping followed by quantitative complementation tests to deficiencies and mutations is an effective strategy for gene discovery that allows characterization of effects of recessive lethal genes on adult phenotypes and here enabled identification of a candidate gene that contributes to sex-specific quantitative variation in olfactory behavior.