A new beetle family Cretohisteridae fam.n. is described from the Lower Cretaceous Yixian Formation (similar to 125 Ma) at Huangbanjigou of Beipiao City, Liaoning Province, Northeastern China based on a well preserved fossil beetle, Cretohister sinensis gen., sp.n. This discovery has established the oldest fossil record for the superfamily Histeroidea, backdating the minimum age of the group by 25 Ma from the earliest Cenomanian (similar to 99 Ma) to the Barremian of the Cretaceous Period. Based on cladistic analyses of a comprehensive morphological dataset, Cretohisteridae is unambiguously recovered as the sister group of Histeridae, exhibiting several character states that bridge the span between Sphaeritidae, Synteliidae and Histeridae. The discovery of the new fossil family sheds new light on the early evolution and diversity of the Histeroidea in the Early Cretaceous, and provides new clues to solving the long-ambiguous phylogenetic relationships among the modern families of Histeroidea.