A new millipede species of the genus Sechelleptus Mauriès, 1980 is described and illustrated from Mayotte Island, Indian Ocean. This new species, S. arborivagus sp. nov., found on trees, looks particularly similar to the sympatric S. variabilisVandenSpiegel & Golovatch, 2007, but is much larger and has a very different ecological behavior. Phylogenetic analyses based on a concatenated dataset of the COI and 16S rRNA genes and including nine species of Spirostreptidae (including Sechelleptus,Doratogonus Attems, 1914, Bicoxidens Attems, 1928andSpirostreptus Brandt, 1833), strongly support the monophyly of Sechelleptus. Despite the similarity of their genitalia, the molecular analyses also reveal a clear-cut genetic divergence between S. arborivagus sp. nov. and S. variabilis (22.55% for COI and 6.63% for 16SrRNA) and further suggest the presence of a higher diversity within the genus Sechelleptuson Mayotte.