Brain size is under many opposing selection pressures. Estimating their relative influence and reconstructing the brain's evolutionary history have, however, proved difficult. Here, we confirm the suggestion that the brain of brood parasitic cuckoos is smaller in relation to their body weight than that of nonparasitic cuckoo species. Two hypotheses explaining reductions in brain size are tested, using phylogenetically controlled correlations and evolutionary pathway analyses. In a novel approach, the pathway models are combined to build the most likely evolutionary sequence of trait changes correlating with changes in brain size. Brain size changed before brood parasitism, followed by a shift toward less-productive habitats and an increase in migration. This sequence shows that brain size was not reduced as a consequence of a loss of cognitive skills related to chick provisioning, and it offers no support for the hypothesis that an increase in energetic demands or a reduction in energy availability selected for a reduction of brain size. Instead, the sequence suggests that the reduction in energetic demands due to the smaller brain size and parasitic breeding strategy may have enabled parasitic cuckoos to colonize new niches.