The redescription of the cranial anatomy of Belebey vegrandis, a Permian bolosaurid reptile from southern Russia, provides valuable new information for determining the phylogenetic relationships of this enigmatic group of early amniotes. As exemplified by the superbly preserved skulls and mandibles of Belebey, bolosaurids are characterized by the following attributes: the presence of a unique, heterodont marginal dentition; a slender, anteroposteriorly elongate lower temporal fenestra that is bound mainly by the quadratojugal and squamosal bones; a large coronoid process formed by three bones; a splenial that is restricted to the ventral surface of the mandible; and a long anterior process of the prearticular that covers much of the medial surface of the dentary bone. The palate of Belebey appears to be greatly modified in the region of the snout, indicating the presence of a functional secondary palate. Phylogenetic analysis of Palaeozoic amniotes indicates that bolosaurids are parareptiles and the sister taxon to the clade comprised of Macroleter, Procolophonia, and Pareiasauria. This position, which is high within Parareptilia, necessitates long ghost lineages for several Late Permian Russian and South African taxa, because the oldest known bolosaurids have been found close to the Permo–Carboniferous boundary in New Mexico. © 2007 The Linnean Society of London, Zoological Journal of the Linnean Society, 2007, 151, 191–214.