The centipede genus Eupolybothrus Verhoeff, 1907 in North Africa is revised. A new cavernicolous species, E. kahfi Stoev & Akkari, sp. n., is described from a cave in Jebel Zaghouan, northeast Tunisia. Morphologically, it is most closely related to E. nudicornis (Gervais, 1837) from North Africa and Southwest Europe but can be readily distinguished by the long antennae and leg-pair 15, a conical dorso-median protuberance emerging from the posterior part of prefemur 15, and the shape of the male first genital sternite. Molecular sequence data from the cytochrome c oxidase I gene (mtDNA–5’ COI-barcoding fragment) exhibit 19.19% divergence between E. kahfi and E. nudicornis, an interspecific value comparable to those observed among four other species of Eupolybothrus which, combined with a low intraspecific divergence (0.3-1.14%), supports the morphological diagnosis of E. kahfi as a separate species. This is the first troglomorphic myriapod to be found in Tunisia, and the second troglomorph lithobiomorph centipede known from North Africa. E. nudicornis is re-described based on abundant material from Tunisia and its post-embryonic development, distribution and habitat preferences recorded. E. cloudsley-thompsoni Turk, 1955, a nominal species based on Tunisian type material, is placed in synonymy with E. nudicornis. To comply with the latest technological developments in publishing of biological information, the paper implements new approaches in cybertaxonomy, including database and interactive key publishing, georeferencing of all localities via Google Earth, and ZooBank, GenBank and MorphBank registration of datasets. An interactive key to all valid species of Eupolybothrus is made with DELTA software.