The enigmatic millipede assassin bug genus Xenorhyncocoris Miller, 1938 is revised. Previously known species, X. caraboides Miller, 1938, X. princeps Miller, 1949 and X. schoenitzeri Putshkov & Bérenger, 1999, are diagnosed and photographed. A new species, X. attractivus sp. nov., is described based on male and female specimens from northeastern Borneo. The male of Xenorhyncocoris is reported for the first time, revealing the extreme sexual dimorphism present in the genus. The diagnosis of Xenorhyncocoris is extended in order to make it applicable to the new discovery, and a female-based key to species of the genus is updated. Relationships among Xenorhyncocoris and Vilius Stål, 1863, Neozirta Distant, 1919 and Schottus Distant, 1902 are briefly discussed.