Encephalization, or brain expansion, underpins humans' sophisticated social cognition, including language, joint attention, shared goals, teaching, consensus decision-making and empathy. These abilities promote and stabilize cooperative social interactions, and have allowed us to create a 'cognitive' or 'cultural' niche and colonize almost every terrestrial ecosystem. Cetaceans (whales and dolphins) also have exceptionally large and anatomically sophisticated brains. Here, by evaluating a comprehensive database of brain size, social structures and cultural behaviours across cetacean species, we ask whether cetacean brains are similarly associated with a marine cultural niche. We show that cetacean encephalization is predicted by both social structure and by a quadratic relationship with group size. Moreover, brain size predicts the breadth of social and cultural behaviours, as well as ecological factors (diversity of prey types and to a lesser extent latitudinal range). The apparent coevolution of brains, social structure and behavioural richness of marine mammals provides a unique and striking parallel to the large brains and hyper-sociality of humans and other primates. Our results suggest that cetacean social cognition might similarly have arisen to provide the capacity to learn and use a diverse set of behavioural strategies in response to the challenges of social living.