We provide new morphological and genetic data on a poorly studied genus of geckos from Madagascar (Paragehyra) previously thought to be distributed only in the southeast and southwest of the island and discuss the biogeography and evolution of this genus. Two species (Paragehyra petiti and Paragehyra gabriellae) were formerly included in this genus, whose phylogenetic and biogeograph-ical relationships remain unresolved. This morphological and molecular study enables the recognition of two new rock-dwelling species that are here formally described. Paragehyra felicitae sp. nov. has only been observed in the private Anja reserve and nearby areas (close to Ambalavao) on the southern central high plateau of Madagascar, whereas Paragehyra austini sp. nov. is known from only one locality on the western slopes of the Andohahela massif, around 60 km northwest of Tolagnaro. The four species differ from one another by a combination of several morphological characters, genetic divergence >5.2 % in a mitochondri-al 16S ribosomal RNA (rRNA) gene fragment and nucleotide differences in analysed nuclear genes, as highlighted in the resulting phylogenetic reconstruction and haplotype network analysis. A further, hitherto un-studied Paragehyra population is known from the Tsingy de Bemaraha in central-western Madagascar. Preliminary information of its morphological differentiation are here provided and suggest that this undescribed species is closely related to P. petiti and P. felicitae sp. nov. Electronic supplementary material The online version of this article (doi:10.1007/s13127-014-0191-5) contains supplementary material, which is available to authorized users.