Two fragments of millipedes, referred to the genus Archispirostreptus, are reported from an archaeological site in the Tadrart Acacus region of southwestern Libya. Radiocarbon dating of the specimens shows that one of them dates to between ca. 9100 and 8800 years ago, and the other one between 6400 and 6300 years ago (calibrated dates). The site lies far from known present-day occurrences of spirostreptid millipedes, and the Libyan subfossils probably, like other isolated occurrences of Archispirostreptus species in the Sahara and the Middle East, represent geographical relicts of a former, continuous distribution. The millipedes were probably able to survive at the Libyan site during the early and middle Holocene periods thanks to the more humid conditions, and may descend from animals that initially colonised the area during the even more humid, and longer, last interglacial period.