Odontocetes (toothed whales) rely upon echoes of their own vocalizations to navigate and find prey underwater [1]. This sensory adaptation, known as echolocation, operates most effectively when using high frequencies, and odontocetes are rivaled only by bats in their ability to perceive ultrasonic sound greater than 100 kHz [2]. Although features indicative of ultrasonic hearing are present in the oldest known odontocetes [3], the significance of this finding is limited by the methods employed and taxa sampled. In this report, we describe a new xenorophid whale (Echovenator sandersi, gen. et sp. nov.) from the Oligocene of South Carolina that, as a member of the most basal clade of odontocetes, sheds considerable light on the evolution of ultrasonic hearing. By placing high-resolution CT data from Echovenator sandersi, 2 hippos, and 23 fossil and extant whales in a phylogenetic context, we conclude that ultrasonic hearing, albeit in a less specialized form, evolved at the base of the odontocete radiation. Contrary to the hypothesis that odontocetes evolved from low-frequency specialists [4], we find evidence that stem cetaceans, the archaeocetes, were more sensitive to high-frequency sound than their terrestrial ancestors. This indicates that selection for high-frequency hearing predates the emergence of Odontoceti and the evolution of echolocation.