The skull of a small anomodont therapsid, from the Tapinocephalus Assemblage Zone (Abrahamskraal Formation, Beaufort Group, Upper Permian) in Northern Cape Province, South Africa, represents a new basal dicynodont and is described in detail. Colobodectes cluveri gen. et sp. nov. is distinguished from other dicynodonts by an anteroposteriorly extensive caniniform process, parietals that were broadly overlapped posterolaterally by posterodorsal processes of the postorbitals, diverging anterior palatal ridges, and a dorsoventrally low foramen magnum. A phylogenetic analysis indicates that Colobodectes is the basalmost member of a dicynodont clade that excludes Eodicynodon. This position is not particularly strong, as two additional steps are needed to make Colobodectes and Eodicynodon oosthuizeni exchange places on the most parsimonious tree. Another discovery of the phylogenetic analysis is that there is little basis for recognizing Eodicynodon oelofseni as the closest relative of E. oosthuizeni. The former species is identified as the sister taxon of a clade that includes the latter and all other dicynodonts.