The anatomy of African lacertid lizards (Lacertidae: Eremiadini) is poorly known, which has hindered a better understanding of their evolutionary relationships. This applies especially to the East African clade, which includes the genera Nucras, Latastia, Philochortus, Pseuderemias and Heliobolus. We present a detailed description of the skull osteology of the genus Heliobolus using X-ray microcomputed tomography and compare its morphology to the above lacertid taxa. Because the genus Heliobolus includes species of doubtful validity and affinities (Heliobolus neumanni and Heliobolus nitidus), we also present a detailed intrageneric comparison and construct a morphological character matrix that we analyse against a phylogenetic backbone derived from previous molecular studies. Heliobolus lugubris and Heliobolus spekii can be well characterised as a monophyletic group on the basis of a short postorbital and a continuously broad posterior margin of the parietal, differing from H. nitidus and other members of the East African clade in an overall low degree of ossification and reduced ventral extension of the frontal bone. Our preliminary phylogenetic analysis suggests that the genus Heliobolus is currently polyphyletic. We propose that the name H. neumanni be officially retracted, because specimens assigned to this species show very different morphologies relative to each other and are placed in different parts of the tree in our analysis. Also, the type specimen is lost and no specimens were collected from the type locality. H. nitidus shows a signal towards the genus Latastia. A definitive, new generic assignment of H. nitidus must await further investigations based on molecular data.