In this study, we provide an extended multilocus phylogenetic analysis combining mitochondrial and nuclear DNA of a group of fossorial and miniaturized legless lizards (genus Paracontias) from Madagascar, including the description of two species new to science, P. ampijoroensis sp. nov. and P. mahamavo sp. nov. Our analyses revealed the existence of two distinct, parapatric and diagnosable clades within the genus: (i) the ‘kankana clade’ (including P. kankana and the two newly described species), located in the north (but absent from the extreme northern tip) of the island and characterized by a pattern of cephalic scales very unusual for Malagasy Scincinae, with large loreal scales extending to and meeting each other at dorsal midline, and (ii) the ‘brocchii clade’ (including all other studied species), endemic to the north of Madagascar and characterized by small loreal scales separated from each other by the rostral and the frontonasal scale. By combining phylogenetic results with morphological traits observed among species, we develop novel hypotheses on the simplification of the cephalic scalation pattern within this genus, a trend frequently encountered among various lineages of legless squamates that convergently adapted to a burrowing lifestyle. Additionally, a user-friendly graphical identification key for species of Paracontias is provided and made available as supplementary information.