Adaptive evolution of animals depends on behaviors that are essential for their survival and reproduction. Adaptive evolution has resulted in diverse chemoreceptor families, in which polymorphisms contribute to individual variation in chemosensation, while simultaneously preserving comprehensive chemosensory ability through combinatorial odorant recognition in a functionally redundant system. Odorant binding proteins (OBPs) are the first components of the insect olfactory system to encounter odorants. Despite their abundant expression, little is known about their role in chemosensation, largely due to the lack of available mutations in these genes. We capitalized on naturally occurring mutations (polymorphisms) to gain insights into their functions. We analyzed the sequences of 13 Obp genes in two chromosomal clusters in a population of wild-derived inbred lines, and asked whether polymorphisms in these genes are associated with variation in olfactory responsiveness. Four polymorphisms in three Obp genes exceeded the statistical permutation threshold for association with responsiveness to benzaldehyde, suggesting redundancy and/or combinatorial recognition by these Obps of this odorant. Model predictions of alternative pre-mRNA secondary structures associated with polymorphic sites suggest that alterations in Obp mRNA structure could contribute to phenotypic variation in olfactory behavior. Furthermore, to gain insights into the genetic determinants of individual variation in odorant recognition, we measured olfactory responses to a structurally similar odorant, acetophenone, in a population of 297 inbred wild-derived lines of Drosophila melanogaster. We identify six different SNPs in the same Obps that are associated with variation in responses to a structurally similar odorant, acetophenone. Five SNPs are in coding regions of Obp99b and Obp99d and one SNP is in the 3’untranslated region of Obp99a (A610G). Surprisingly, the 610G allele is associated with higher response scores to acetophenone than the 610A allele, but lower expression of Obp99a. Furthermore, RNAi-mediated reduction of Obp99d expression results in reduced behavioral responses to acetophenone. Thus, the same OBPs contribute to combinatorial odorant recognition, but different SNPs generate odorant-specific individual variation. Dual olfactory recognition where OBPs regulate odorant access to receptors may enhance discrimination and help explain discrepancies between electrophysiologically determined odorant receptor response profiles and behavioral measurements.