The skeleton of a eutherian (placental) mammal has been discovered from the Lower Cretaceous Yixian Formation of northeastern China. We estimate its age to be about 125 million years (Myr), extending the date of the oldest eutherian records with skull and skeleton by about 40 50 Myr. Our analyses place the new fossil at the root of the eutherian tree and among the four other known Early Cretaceous eutherians, and suggest an earlier and greater diversification of stem eutherians that occurred well before the molecular estimate for the diversification of extant placental superorders (104 64 Myr). The new eutherian has limb and foot features that are known only from scansorial (climbing) and arboreal (tree-living) extant mammals, in contrast to the terrestrial or cursorial (running) features of other Cretaceous eutherians. This suggests that the earliest eutherian lineages developed different locomotory adaptations, facilitating their spread to diverse niches in the Cretaceous.