A new taxon of early cynodont, Abdalodon diastematicus gen. et sp. nov., is described. The new taxon is represented by a single skull from the upper Permian Tropidostoma Assemblage Zone (AZ) of the Beaufort Group (Karoo Basin, South Africa), which was previously referred to Procynosuchus delaharpeae. Abdalodon is distinguished from Procynosuchus by the presence of only four upper and three lower incisors, fewer postcanines, a well-developed depression on the lateral surface of the maxilla posterior to the canine root, a tall mandibular symphysis forming a distinct ‘chin’, a relatively short snout, and weak or absent interdigitation of sutures in the interorbital region. These features are shared with the only other Tropidostoma AZ cynodont, Charassognathus gracilis. Abdalodon is distinguished from Charassognathus by its postcanine morphology, the presence of an expanded masseteric fossa, inset postcanine tooth rows, a broader interorbital region, and proportionally shorter temporal region. Most strikingly, Abdalodon has a lengthy diastema between the canines and postcanines on both the maxilla and the dentary. Charassognathus has a short diastema between the upper canine and postcanines, but not the lowers, and diastemata are absent from the tooth rows of Procynosuchus. Phylogenetic analysis recovers Abdalodon as the sister-taxon of Charassognathus, forming a clade (Charassognathidae fam. nov.) at the base of Cynodontia. These taxa represent a previously unrecognized radiation of small-bodied Permian cynodonts. Despite their small size, the holotypes of Abdalodon and Charassognathus probably represent adults and indicate that early evolution of cynodonts may have occurred at small body size, explaining the poor Permian fossil record of the group.