Pycnotarsobrentus inuiae Maruyama & Bartolozzi, gen. nov. and sp. nov. (Brentinae: Eremoxenini) is described from the Lambir Hills National Park, Borneo (Sarawak, Malaysia) based on specimens collected from Crematogaster difformis F. Smith, 1857 ant nests in the myrmecophytic epiphytic ferns Platycerium crustacea Copel. and Lecanopteris ridleyi H. Christ. A second species of Pycnotarsobrentus is known from Malaysia but is represented by only one female and consequently not yet described pending discovery of a male. Pycnotarsobrentus belongs to the tribe Eremoxenini and shares some character states with the African genus Pericordus Kolbe, 1883. No species of Eremoxenini with similar morphological modifications are known from the Oriental region.