Laos has large areas of primary forest with a largely unexplored fauna. This is evidenced by millipedes, class Diplopoda, with fewer than 60 species being recorded from the country. In the widespread Southeast Asian “Star Millipede” genus Eutrichodesmus Silvestri, 1910 (family Haplodesmidae), only two of 49 recorded species have been found in Laos. Four new species of Star Millipedes are here described from caves in Laos: Eutrichodesmus steineri Liu & Wesener, sp. n., E. deporatus Liu & Wesener, sp. n., E. paraster Liu & Wesener, sp. n. and E. parvus Liu & Wesener, sp. n.. A fifth species, for which only a female is available, remains unnamed. The defensive glands (ozopores) are found to be strongly or entirely suppressed in two of the new species, E. deporatus Liu & Wesener, sp. n. and E. paraster Liu & Wesener, sp. n., both troglobionts, which is new to the family. All of the Star Millipedes were collected during Northern Lao-European Cave Project faunal surveys conducted by the Senckenberg Museum, Frankfurt. A key to the six species of Eutrichodesmus currently known to occur in Laos is provided.