Eight species of polydesmoid millipeds are described from the caves of the extreme northwestern corner of Papua New Guinea. Four new genera are named: in Paradoxosomatidae, Selminosoma, type S. chapmani; Astromontosoma, type A. jeekeli; in Doratodesmidae, Scolopopyge, type S. pholeter; Selminarchus, type S. hispidus. Two additional new species are referred to established genera Eustrongylosoma exiguum and Nothrosoma beroni, the latter, however, (known only from females) is probably referable to a new genus. Selminosoma chapmani appears both from its structure and biology to be a true troglobite, the first such species known in the Paradoxosomatidae. The two doratodesmid species extend the known range of this family eastward across Wallace’s Line from west Java.