Adaptive evolution of animals depends on behaviors that are essential for their survival and reproduction. The olfactory system of Drosophila melanogaster has emerged as one of the best characterized olfactory systems, which in addition to a family of odorant receptors, contains an approximately equal number of odorant-binding proteins (OBPs), encoded by a multigene family of 51 genes. 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 3 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.