The present study explored the diversity of Nannocharax within southern Africa by implementing three species delimitation methods for a data set consisting of 37 mitochondrial cytochrome oxidase subunit I sequences. Two unilocus coalescent methods, the General Mixed Yule Coalescent (GMYC) and the Bayesian implementation of the Poisson Tree Processes (bPTP), and a genetic distance method, the Automatic Barcode Gap Discovery (ABGD), were applied. Both GMYC and bPTP delimited the same operational taxonomic units (OTUs), revealing a higher diversity for the genus in the region than previously recognised, whereas the ABGD failed to delimit the same candidate species. All methods delimited two species groups, and these are supported based on colouration patterning and morphology; the Nannocharax multifasciatus and the Nannocharax macropterus species groups and the delimited OTUs were assigned to each. Two putative new species were identified, Nannocharax cf. lineostriatus Okavango from the Okavango River in Angola and N. cf. lineostriatus Kwanza from the Kwanza River system in Angola. The distribution of Nannocharax dageti was confirmed for the Upper Zambezi and extended to the Okavango system, and an identification key for the southern Africa Nannocharax species is provided.