Evolutionary shifts in plant-herbivore interactions provide a model for understanding the link among the evolution of behaviour, ecological specialization and incipient speciation. Drosophila mojavensis uses different host cacti across its range, and volatile chemicals emitted by the host are the primary cue for host plant identification. In this study, we show that changes in host plant use between distinct D. mojavensis populations are accompanied by changes in the olfactory system. Specifically, we observe differences in olfactory receptor neuron specificity and sensitivity, as well as changes in sensillar subtype abundance, between populations. Additionally, RNA-seq analyses reveal differential gene expression between populations for members of the odorant receptor gene family. Hence, alterations in host preference are associated with changes in development, regulation and function at the olfactory periphery.