As the brain is responsible for managing an individual's behavioral response to its environment, we should expect that large relative brain size is an evolutionary response to cognitively challenging behaviors. The "social brain hypothesis" argues that maintaining group cohesion is cognitively demanding as individuals living in groups need to be able to resolve conflicts that impact on their ability to meet resource requirements. If sociality does impose cognitive demands, we expect changes in relative brain size and sociality to be coupled over evolutionary time. In this study, we analyze data on sociality and relative brain size for 206 species of ungulates, carnivores, and primates and provide, for the first time, evidence that changes in sociality and relative brain size are closely correlated over evolutionary time for all three mammalian orders. This suggests a process of coevolution and provides support for the social brain theory. However, differences between taxonomic orders in the stability of the transition between small-brained/nonsocial and large-brained/social imply that, although sociality is cognitively demanding, sociality and relative brain size can become decoupled in some cases. Carnivores seem to have been especially prone to this.