Palaeodesmus tuberculata is an extinct species of millipede known from the lower Devonian period of modern-day Scotland. It was originally described as "Kampecaris tuberculata" by the Reverend Stanley Graham Brade-Birks, but was placed in its own new genus, Palaeodesmus, in 2004. Palaeodesmus has three rows of tubercles or bosses in the shape of round-edged squares or rectangles on the dorsal portion of each body segment. Palaeodesmus is a member of the extinct group Archipolypoda, but its anatomy is too poorly known to place it confidently within any known taxonomic family or order, and so it remains incertae sedis (uncertain placement), although possibly related to archidesmidan species such as Archidesmus.