The centipede genus Eupolybothrus Verhoeff, 1907 in North Africa is revised. A new cavernicolous species, Eupolybothrus kahfi Stoev & Akkari, sp. n., is described from a cave in Jebel Zaghouan, northeast Tunisia. Morphologically, it is most closely related to Eupolybothrus 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 Eupolybothrus kahfi and Eupolybothrus 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 Eupolybothrus 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. Eupolybothrus nudicornis is redescribed based on abundant material from Tunisia and its post-embryonic development, distribution and habitat preferences recorded. Eupolybothrus cloudsley-thompsoni Turk, 1955, a nominal species based on Tunisian type material, is placed in synonymy with Eupolybothrus nudicornis. To comply with the latest technological developments in publishing of biological information, the paper implements new approaches in cybertaxonomy, such as fine granularity XML tagging validated against the NLM DTD TaxPub for PubMedCentral and dissemination in XML to various aggregators (GBIF, EOL, Wikipedia), vizualisation of all taxa mentioned in the text via the dynamically created Pensoft Taxon Profile (PTP) page, data 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.