Giant pill-millipedes (order Sphaerotheriida) are large-bodied millipedes without poison glands which can roll-up into a complete ball. Their disconnected area of distribution spanning South Africa, Madagascar, India, SE Asia, Australia and New Zealand makes them interesting model organisms for biogeographic studies. The here presented phylogeny is based on a molecular dataset covering all areas of distribution with a special focus on Madagascar, where some species of giant pill-millipedes show island gigantism, reaching the size of a baseball. For our study, two mitochondrial genes (partial 16S rRNA and COI) as well as the complete nuclear 18S rDNA were sequenced. While many recent vertebrate studies hint that the ancestors of the recent Malagasy fauna crossed the >350 km wide Mozambique Channel several times, no such crossing was discovered in the Sphaerotheriida. For the first time in a molecular phylogenetic study of soil arthropods, a Madagascar-India group, the family Arthrosphaeridae, is recovered, hinting to a Gondwanan origin of the Sphaerotheriida. The Malagasy-Indian family Arthrosphaeridae forms a monophyletic, statistically well-supported group in all obtained trees. The giant pill-millipedes from Madagascar are paraphyletic because the Malagasy genus Sphaeromimus is the sister-taxon of the Indian Arthrosphaera. In Sphaeromimus, an ecotone shift occurred only once: the spiny forest species Sphaeromimus musicus forms the sister-clade to the species collected in rainforests and littoral rainforests. The two species of the Malagasy genus Zoosphaerium which express island gigantism form a monophyletic group in some trees, but these trees lack good statistical support. Deeper nodes inside the Sphaerotheriida, like the position of the Australian genera Procyliosoma and Epicyliosoma, the Southeast Asian family Zephroniidae and the South African genus Sphaerotherium could not be resolved. This study is the first genetic study inside the order Sphaerotheriida and provides a proper basis for future molecular biogeographic studies in millipedes and soil organisms from Madagascar. Copyright © 2010 Elsevier Inc. All rights reserved.