Evolution sculpts the olfactory nervous system in response to the unique sensory challenges facing each species. In vertebrates, dramatic and diverse adaptations to the chemical environment are possible because of the hierarchical structure of the olfactory receptor (OR) gene superfamily: rapid growth or pruning across the OR gene tree accompany major changes in habitat and lifestyle; independent selection on OR subfamilies can permit local adaptation or conserved chemical communication; and genetic variation in single OR genes among thousands can alter odor percepts and behaviors driven by precise chemical cues. However, this genetic flexibility contrasts with the relatively fixed neural architecture of the vertebrate olfactory system, whose slower rate of divergence mandates that new olfactory receptors integrate into segregated and functionally-distinct neural pathways. This organization allows evolution to couple critical chemical signals with selectively advantageous responses, but also constrains relationships between olfactory receptors and behavior. The coevolution of the OR repertoire and the structure of the olfactory system therefore reveals general principles of how the brain solves specific sensory problems and how it adapts to new ones.