Little is known about the olfactory capabilities of extinct basal (non-neornithine) birds or the evolutionary changes in olfaction that occurred from non-avian theropods through modern birds. Although modern birds are known to have diverse olfactory capabilities, olfaction is generally considered to have declined during avian evolution as visual and vestibular sensory enhancements occurred in association with flight. To test the hypothesis that olfaction diminished through avian evolution, we assessed relative olfactory bulb size, here used as a neuroanatomical proxy for olfactory capabilities, in 157 species of non-avian theropods, fossil birds and living birds. We show that relative olfactory bulb size increased during non-avian maniraptoriform evolution, remained stable across the non-avian theropod/bird transition, and increased during basal bird and early neornithine evolution. From early neornithines through a major part of neornithine evolution, the relative size of the olfactory bulbs remained stable before decreasing in derived neoavian clades. Our results show that, rather than decreasing, the importance of olfaction actually increased during early bird evolution, representing a previously unrecognized sensory enhancement. The relatively larger olfactory bulbs of earliest neornithines, compared with those of basal birds, may have endowed neornithines with improved olfaction for more effective foraging or navigation skills, which in turn may have been a factor allowing them to survive the end-Cretaceous mass extinction.