The social brain hypothesis posits that the cognitive demands of social behaviour have driven evolutionary expansions in brain size in some vertebrate lineages. In insects, higher brain centres called mushroom bodies are enlarged and morphologically elaborate (having doubled, invaginated and subcompartmentalized calyces that receive visual input) in social species such as the ants, bees and wasps of the aculeate Hymenoptera, suggesting that the social brain hypothesis may also apply to invertebrate animals. In a quantitative and qualitative survey of mushroom body morphology across the Hymenoptera, we demonstrate that large, elaborate mushroom bodies arose concurrent with the acquisition of a parasitoid mode of life at the base of the Euhymenopteran (Orussioidea + Apocrita) lineage, approximately 90 Myr before the evolution of sociality in the Aculeata. Thus, sociality could not have driven mushroom body elaboration in the Hymenoptera. Rather, we propose that the cognitive demands of host-finding behaviour in parasitoids, particularly the capacity for associative and spatial learning, drove the acquisition of this evolutionarily novel mushroom body architecture. These neurobehavioural modifications may have served as pre-adaptations for central place foraging, a spatial learning-intensive behaviour that is widespread across the Aculeata and may have contributed to the multiple acquisitions of sociality in this taxon.