Mammals are the most encephalized vertebrates, with the largest brains relative to body size. Placental mammals have particularly enlarged brains, with expanded neocortices for sensory integration, the origins of which are unclear. We used computed tomography scans of newly discovered Paleocene fossils to show that contrary to the convention that mammal brains have steadily enlarged over time, early placentals initially decreased their relative brain sizes because body mass increased at a faster rate. Later in the Eocene, multiple crown lineages independently acquired highly encephalized brains through marked growth in sensory regions. We argue that the placental radiation initially emphasized increases in body size as extinction survivors filled vacant niches. Brains eventually became larger as ecosystems saturated and competition intensified.