We here describe a new Early Cretaceous (early Albian) eutherian mammal, Sasayamamylos kawaii gen. et sp. nov., from the 'Lower Formation' of the Sasayama Group, Hyogo Prefecture, Japan. Sasayamamylos kawaii is characterized by a robust dentary, a distinct angle on the ventral margin of the dentary at the posterior end of the mandibular symphysis, a lower dental formula of 3-4 : 1 : 4 : 3, a robust lower canine, a non-molariform lower ultimate premolar, and a secondarily reduced entoconid on the molars. To date, S. kawaii is the earliest known eutherian mammal possessing only four premolars, which demonstrates that the reduction in the premolar count in eutherians started in the late Early Cretaceous. The occurrence of S. kawaii implies that the relatively rapid diversification of eutherians in the mid-Cretaceous had already started by the early Albian.