Two new species of the millipede order Polydesmida are described from primary rainforest litter on the slope of Mount Salak, an active volcano in western Java, Indonesia. Circulocyptus javanicus n. sp. differs from C. faillei Golovatch, 2016, the sole, and type, species of the genus Circulocyptus Golovatch, 2016, family Cryptodesmudae, known from several places in central and southern Vietnam, by the much larger body (ca 20 vs. 11-16 mm long), more numerous radii at the anterior margin of the collum (29 vs. 25), more abundant metatergal tubercles (usually 6 vs. 4 rows), the shape of the lateral margin of paraterga (anterolateral corner mostly broadly rounded vs. squarish), and minor details of gonopodal structure. The diagnosis of Circulocyptus is refined since this genus seems to be unique not only within the family, but also amongst the entire Polydesmida in showing an accessory seminal chamber located not at the end of a solenomere, which is a typical situation, but on a separate gonopodal branch and lying just opposite the solenomere tip. Cylindrodesmus telnovorum n. sp. is only a third species to be recognized in Cylindrodesmus Pocock, 1889, family Haplodesmudae, a genus which presently encompasses the type species C. hirsutus Pocock, 1889, nearly ubiquitous, mostly pantropical and partly parthenogenetic, and C. villosus Pocock, 1898, from Rotuma Island, Fiji, southwestern Pacific. The new species differs from both primarily by the peculiar colour pattern (mainly blackish contrasting with pinkish) and uniramous gonopod (much like in C. hirsutus, but gradually attenuating in distal half until a blunt tip).