Colonization of a novel ecological niche can require, or be driven by, evolution of an animal's behaviors promoting their reproductive success. We investigated the evolution and sensory basis of oviposition in Drosophila sechellia, a close relative of Drosophila melanogaster that exhibits extreme specialism for Morinda citrifolia noni fruit. D. sechellia produces fewer eggs than other drosophilids and lays these almost exclusively on noni substrates. We show that visual, textural and social cues do not explain this species-specific preference. By contrast, we find that loss of olfactory input in D. sechellia, but not D. melanogaster, essentially abolishes egg-laying, suggesting that olfaction gates gustatory-driven noni preference. Noni odors are detected by redundant olfactory pathways, but we discover a role for hexanoic acid and the cognate Ionotropic receptor 75b (Ir75b) in odor-evoked oviposition. Through receptor exchange in D. melanogaster, we provide evidence for a causal contribution of odor-tuning changes in Ir75b to the evolution of D. sechellia's oviposition behavior.