Cetaceans possess brains that rank among the largest to have ever evolved, either in terms of absolute mass or relative to body size. Cetaceans have evolved these huge brains under relatively unique environmental conditions, making them a fascinating case study to investigate the constraints and selection pressures that shape how brains evolve. Indeed, cetaceans have some unusual neuroanatomical features, including a thin but highly folded cerebrum with low cortical neuron density, as well as many structural adaptations associated with acoustic communication. Previous reports also suggest that at least some cetaceans have an expanded cerebellum, a brain structure with wide-ranging functions in adaptive filtering of sensory information, the control of motor actions, and cognition. Here, we report that, relative to the size of the rest of the brain, both the cerebrum and cerebellum are dramatically enlarged in cetaceans and show evidence of co-evolution, a pattern of brain evolution that is convergent with primates. However, we also highlight several branches where cortico-cerebellar co-evolution may be partially decoupled, suggesting these structures can respond to independent selection pressures. Across cetaceans, we find no evidence of a simple linear relationship between either cerebrum and cerebellum size and the complexity of social ecology or acoustic communication, but do find evidence that their expansion may be associated with dietary breadth. In addition, our results suggest that major increases in both cerebrum and cerebellum size occurred early in cetacean evolution, prior to the origin of the major extant clades, and predate the evolution of echolocation.