A new genus of velvety shore bugs, Pristinochterus gen. n., with one new species, Pristinochterus zhangi sp. n., are described. The specimens were collected from the Late Jurassic to Early Cretaceous Yixian Formation and Early Cretaceous Jiufotang Formation in northeastern China. This finding represents the first record of fossil velvety shore bugs from China. Among the specimens, four well-preserved nymphs are reported for the first time. The placement of the new genus within Ochteridae is briefly discussed. A key to the world genera of Ochteridae is provided.