Toothed whales (order Cetacea: suborder Odontoceti) are highly encephalized, possessing brains that are significantly larger than expected for their body sizes. In particular, the odontocete superfamily Delphinoidea (dolphins, porpoises, belugas, and narwhals) comprises numerous species with encephalization levels second only to modern humans and greater than all other mammals. Odontocetes have also demonstrated behavioral faculties previously only ascribed to humans and, to some extent, other great apes. How did the large brains of odontocetes evolve? To begin to investigate this question, we quantified and averaged estimates of brain and body size for 36 fossil cetacean species using computed tomography and analyzed these data along with those for modern odontocetes. We provide the first description and statistical tests of the pattern of change in brain size relative to body size in cetaceans over 47 million years. We show that brain size increased significantly in two critical phases in the evolution of odontocetes. The first increase occurred with the origin of odontocetes from the ancestral group Archaeoceti near the Eocene-Oligocene boundary and was accompanied by a decrease in body size. The second occurred in the origin of Delphinoidea only by 15 million years ago.