A taxonomic revision of the Cardiocondyla nuda species group is presented based on methods of Numeric Morphology-Based Alpha-Taxonomy (NUMOBAT) and supplemented by analysis of mtDNA. A total of 258 samples with 571 worker individuals were investigated by the hierarchical and non-hierarchical exploratory data analyses NC-Ward and NC-K-Means clustering considering 16 NUMOBAT characters. Two species are described as new, increasing the number of species in the group to eight. We separate the group into two main clades: the C. mauritanica species complex, which is of Oriental and Indo-Australian origin and contains the cryptic species C. mauritanica Forel 1890, C. strigifrons Viehmeyer 1922, C. kagutsuchi Terayama 1999, and C. itsukii sp. nov. and the Australasian and Polynesian C. nuda species complex with the cryptic species C. nuda (Mayr 1866), C. atalanta Forel 1915, C. paranuda Seifert 2003, and C. compressa sp. nov. The mean error of the two NC-clustering methods relative to the controlling linear discriminant analysis was 0.4% in C. mauritanica, 2.2% in C. itsukii, 0% in C. strigifrons, 0% in C. kagutsuchi, 1.5% in C. nuda, 3.2% in C. atalanta and 3.2% in C. paranuda—all these data are below the 4% threshold recommended by the Pragmatic Species Concept. The morphologically determined species clusters were confirmed by mtDNA data with a rather strong sequence divergence among the cryptic species of the C. nuda complex of 5.6–7.9%. The mean mismatch of two different mtDNA analyses with NUMOBAT clustering was 5.4% in 54 samples of seven species of the C. nuda group for which mtDNA data were available. The mismatch thus is smaller than in many other studies of Eumetazoa in general or ants in particular and is probably explained by low frequencies of ancient hybridization and/or incomplete lineage sorting. Comments on zoogeography, colony demography and behavior are given in the species sections and determination keys are provided. Cardiocondyla ectopia Snelling 1974 and Leptothorax caparica Henin, Paiva & Collingwood 2002 (syn nov.) are synonymized under Cardiocondyla mauritanica. Cardiocondyla nuda sculptinodis is not a member of the C. nuda group and is moved to C. shuckardi sculptinodis, a revived combination.