Relative brain sizes in birds can rival those of primates, but large-scale patterns and drivers of avian brain evolution remain elusive. Here, we explore the evolution of the fundamental brain-body scaling relationship across the origin and evolution of birds. Using a comprehensive dataset sampling> 2,000 modern birds, fossil birds, and theropod dinosaurs, we infer patterns of brain-body co-variation in deep time. Our study confirms that no significant increase in relative brain size accompanied the trend toward miniaturization or evolution of flight during the theropod-bird transition. Critically, however, theropods and basal birds show weaker integration between brain size and body size, allowing for rapid changes in the brain-body relationship that set the stage for dramatic shifts in early crown birds. We infer that major shifts occurred rapidly in the aftermath of the Cretaceous-Paleogene mass extinction within Neoaves, in which multiple clades achieved higher relative brain sizes because of a reduction in body size. Parrots and corvids achieved the largest brains observed in birds via markedly different patterns. Parrots primarily reduced their body size, whereas corvids increased body and brain size simultaneously (with rates of brain size evolution outpacing rates of body size evolution). Collectively, these patterns suggest that an early adaptive radiation in brain size laid the foundation for subsequent selection and stabilization.