The taxa Cubicostissus palaeocaeni gen. et sp. nov. are described from the Paleocene of Menat (Central France) as the oldest representative of the family Issidae for which all currently known fossils are reviewed. With a unique combination of characters, the specimen represents the first fossil described for the tribe Hysteropterini. Its occurrence in the European Paleocene shows that its lineage, and therefore the Issidae, were already present at least some 60 Ma. It allows to discard the hypothesis of an Eocene origin for the family, which is in accordance with a recent molecular calibration of the family, reporting the tribe as old as the Upper Cretaceous.