The 'Age of Mammals' began in the Paleocene epoch, the 10 million year interval immediately following the Cretaceous-Palaeogene mass extinction. The apparently rapid shift in mammalian ecomorphs from small, largely insectivorous forms to many small-to-large-bodied, diverse taxa has driven a hypothesis that the end-Cretaceous heralded an adaptive radiation in placental mammal evolution. However, the affinities of most Paleocene mammals have remained unresolved, despite significant advances in understanding the relationships of the extant orders, hindering efforts to reconstruct robustly the origin and early evolution of placental mammals. Here we present the largest cladistic analysis of Paleocene placentals to date, from a data matrix including 177 taxa (130 of which are Palaeogene) and 680 morphological characters. We improve the resolution of the relationships of several enigmatic Paleocene clades, including families of 'condylarths'. Protungulatum is resolved as a stem eutherian, meaning that no crown-placental mammal unambiguously pre-dates the Cretaceous-Palaeogene boundary. Our results support an Atlantogenata-Boreoeutheria split at the root of crown Placentalia, the presence of phenacodontids as closest relatives of Perissodactyla, the validity of Euungulata, and the placement of Arctocyonidae close to Carnivora. Periptychidae and Pantodonta are resolved as sister taxa, Leptictida and Cimolestidae are found to be stem eutherians, and Hyopsodontidae is highly polyphyletic. The inclusion of Paleocene taxa in a placental phylogeny alters interpretations of relationships and key events in mammalian evolutionary history. Paleocene mammals are an essential source of data for understanding fully the biotic dynamics associated with the end-Cretaceous mass extinction. The relationships presented here mark a critical first step towards accurate reconstruction of this important interval in the evolution of the modern fauna.