An eulimid gastropod, Megadenus atrae n. sp., endoparasitic in the cloacal chamber of the black sea cucumber Holothuria atra Jaeger is described from Okinawa, Japan, as the fifth species of the genus. Conspecific specimens have also been found from southeast India, northeast Australia and New Caledonia. The generic assignment is justified by the presence of (i) a thick, long proboscis that bears a large fold (pseudopallium) near the base and a collar-like structure at the middle, (ii) a thin, globose shell that is covered by the pseudopallium, and (iii) sexual dimorphism with the female generally larger than the male. The new species is distinguishable from the four previously described congeners by its cauldron-shaped pseudopallium, moderately-developed collar of the proboscis and rounded basal lip of the shell. The comparisons of the size and sex of solitary and paired individuals support a previous hypothesis that the species of Megadenus Ros,n, 1910 are protandrous with environmental sex determination. The present species occurs mostly as monogamous pairs despite its very low population density, implying that the presence of a conspecific individual acts as a cue for larval settlement. Both mechanisms would increase individual reproductive success in such permanent parasites with low prevalence and abundance as the species of Megadenus.