The evolution of air breathing in marine fish was an important step leading to the vertebrate colonization of land. Yet this innovation had a significant impact on the nature of a primary source of sensory information: olfaction. The move to land necessitated the evolution of the nose, a new structure needed to mediate previously independent functions, olfaction and respiration. These disparate functions have recently been shown to be critical to memory processing in the mammalian brain. I will propose that the links between olfaction, respiration and memory can be explained by their shared evolutionary history.