African mole-rats (Bathyergidae, Rodentia) of the (eu)social genus Fukomys are one of the most speciose mammal genera endemic to Sub-Saharan Africa. Fukomys distributed in the Zambezian phytochorion is characterized by extreme chromosomal variation (2n=40-78). We inferred a molecular phylogeny of Zambezian Fukomys to resolve the interrelationships and the evolutionary history of the known chromosomal races. We sequenced the entire cytochrome b gene (1140bp) for a total of 66 specimens representing 18 karyotypical races from Zambia. An additional 31 sequences were retrieved from GenBank including data on all other chromosomal races. The haplotypes belonging to a small chromosomal race from Salujinga cluster with the Fukomys mechowii (Giant mole-rat) haplotypes. Differential degrees of chromosomal variation are observed among the major mole-rat clades, which is most pertinent when comparing the central Zambezian Fukomys micklemi and the northern Zambezian Fukomys whytei clades. The karyotypically hyper-diverse (12 known chromosomal races) Fukomys micklemi clade shows low levels of cytochrome b sequence divergence. Within the F. whytei clade we find a more conservative pattern of chromosomal diversification (three known chromosomal races) while the levels of sequence divergence are much higher then in the F. micklemi clade. Our results suggest that chromosomal changes may drive phyletic divergence and, eventually, speciation. The observed cladogenetic events during the Plio-Pleistocene within the F. mechowii, F. whytei, F. damarensis and F. micklemi clades appear to coincide with climatically mediated speciation bursts in other savannah dwelling mammals, including hominids. Based on the molecular data presented, combined with morphological and chromosomal data, the taxonomic implication seems to be that Fukomys may contain several (undescribed) cryptic species.