The name “millipede” translates to a thousand feet (from mille “thousand” and pes “foot”). However, no millipede has ever been described with more than 750 legs. We discovered a new record-setting species of millipede with 1,306 legs, Eumillipes persephone, from Western Australia. This diminutive animal (0.95 mm wide, 95.7 mm long) has 330 segments, a cone-shaped head with enormous antennae, and a beak for feeding. A distant relative of the previous record holder, Illacme plenipes from California, it belongs to a different order, the Polyzoniida. Discovered 60 m below ground in a drill hole created for mineral exploration, E. persephone possesses troglomorphic features; it lacks eyes and pigmentation, and it has a greatly elongated body—features that stand in stark contrast to its closest surface-dwelling relatives in Australia and all other members of its order. Using phylogenomics, we found that super-elongation (> 180 segments) evolved repeatedly in the millipede class Diplopoda. The striking morphological similarity between E. persephone and I. plenipes is a result of convergent evolution, probably for locomotion in similar soil habitats. Discovered in the resource-rich Goldfields-Esperance region and threatened by encroaching surface mining, documentation of this species and conservation of its habitat are of critical importance.