The evolution of animal behaviour is poorly understood. Despite numerous correlations between interspecific divergence in behaviour and nervous system structure and function, demonstrations of the genetic basis of these behavioural differences remain rare. Here we develop a neurogenetic model, Drosophila sechellia, a species that displays marked differences in behaviour compared to its close cousin Drosophila melanogaster, which are linked to its extreme specialization on noni fruit (Morinda citrifolia). Using calcium imaging, we identify olfactory pathways in D. sechellia that detect volatiles emitted by the noni host. Our mutational analysis indicates roles for different olfactory receptors in long- and short-range attraction to noni, and our cross-species allele-transfer experiments demonstrate that the tuning of one of these receptors is important for species-specific host-seeking. We identify the molecular determinants of this functional change, and characterize their evolutionary origin and behavioural importance. We perform circuit tracing in the D. sechellia brain, and find that receptor adaptations are accompanied by increased sensory pooling onto interneurons as well as species-specific central projection patterns. This work reveals an accumulation of molecular, physiological and anatomical traits that are linked to behavioural divergence between species, and defines a model for investigating speciation and the evolution of the nervous system.