Toothed whales (odontocetes) make use of high-frequency sounds to echolocate, differing significantly from their sister group baleen whales (mysticetes), which make use of low-frequency sound for long-distance communication. This divergence in auditory ability has led to considerable speculation as to how hearing functioned in the ancestral archaeocetes, and when the specialisations of modern species arose. Numerous studies have attempted to infer auditory capabilities from morphological correlates valid in modern species. Here, we build upon these previous methods with a focus on cochlear structures that have well-understood links to function. We combine this with information on the sound conduction apparatus to chart the evolutionary trajectory of cetacean hearing. Our results suggest an initial move towards low-frequency specialisation in early Eocene cetaceans, which coincides with the appearance of new sound conduction pathways. This paved the way for the later movement towards higher frequency hearing in protocetids, however the ultra-high and low-frequency hearing specialisations of both modern cetacean clades evolved after their divergence. We use this data to test the hypotheses that evolutionary brain size increases in cetaceans were related to the origin of high-frequency echolocation. We show that no shift in relative brain size coincides with any changes towards high-frequency perception. However, this does not rule out a role for other changes in hearing ability such as some simple forms of echolocation, similar to that suggested for hippopotamuses or bowhead whales, which may have been present in even the earliest cetaceans.