Odontocetes (toothed whales, dolphins and porpoises) hunt and navigate through dark and turbid aquatic environments using echolocation; a key adaptation that relies on the same principles as sonar. Among echolocating vertebrates, odontocetes are unique in producing high-frequency vocalizations at the phonic lips, a constriction in the nasal passages just beneath the blowhole, and then using air sinuses and the melon to modulate their transmission. All extant odontocetes seem to echolocate; however, exactly when and how this complex behaviour--and its underlying anatomy--evolved is largely unknown. Here we report an odontocete fossil, Oligocene in age (approximately 28 Myr ago), from South Carolina (Cotylocara macei, gen. et sp. nov.) that has several features suggestive of echolocation: a dense, thick and downturned rostrum; air sac fossae; cranial asymmetry; and exceptionally broad maxillae. Our phylogenetic analysis places Cotylocara in a basal clade of odontocetes, leading us to infer that a rudimentary form of echolocation evolved in the early Oligocene, shortly after odontocetes diverged from the ancestors of filter-feeding whales (mysticetes). This was followed by enlargement of the facial muscles that modulate echolocation calls, which in turn led to marked, convergent changes in skull shape in the ancestors of Cotylocara, and in the lineage leading to extant odontocetes.