Xenodermidae is a generally poorly known lineage of caenophidian snakes found in South, East and Southeast Asia. We report molecular phylogenetic analyses for a multilocus data set comprising all five currently recognised genera and including new mitochondrial and nuclear gene sequence data for the recently described Stoliczkia vanhnuailianai. Our phylogenetic results provide very strong support for the non-monophyly of Stoliczkia, as presently constituted, with S. borneensis being more closely related to Xenodermus than to the Northeast Indian S. vanhnuailianai. Based on phylogenetic relationships and morphological distinctiveness, we transfer Stoliczkia borneensis to a new monotypic genus endemic to Borneo, Paraxenodermus gen. nov. We also present new morphological data for P. borneensis.