The detection of odour stimuli in the environment is universally important for primal behaviours such as feeding, mating, kin interactions and escape responses. Given the ubiquity of many airborne chemical signals and the similar organisation of animal olfactory circuits, a fundamental question in our understanding of the sense of smell is how species-specific behavioural responses to odorants can evolve. Recent comparative genomic, developmental and physiological studies are shedding light on this problem by providing insights into the genetic mechanisms that underlie anatomical and functional evolution of the olfactory system. Here we synthesise these data, with a particular focus on insect olfaction, to address how new olfactory receptors and circuits might arise and diverge, offering glimpses into how odour-evoked behaviours could adapt to an ever-changing chemosensory world.