The Paroedura bastardi clade, a subgroup of the Madagascan gecko genus Paroedura, currently comprises four nominal species: P. bastardi, supposedly widely distributed in southern and western Madagascar, P. ibityensis, a montane endemic, and P. tanjaka and P. neglecta, both restricted to the central west region of the island. Previous work has shown that Paroedura bastardi is a species complex with several strongly divergent mitochondrial lineages. Based on one mitochondrial and two nuclear markers, plus detailed morphological data, we undertake an integrative revision of this species complex. Using a representative sampling for seven nuclear and five mitochondrial genes we furthermore propose a phylogenetic hypothesis of relationships among the species in this clade. Our analyses reveal at least three distinct and independent evolutionary lineages currently referred to P. bastardi. Conclusive evidence for the species status of these lineages comes from multiple cases of syntopic occurrence without genetic admixture or morphological intermediates, suggesting reproductive isolation. We discuss the relevance of this line of evidence and the conditions under which concordant differentiation in unlinked loci under sympatry provides a powerful approach to species delimitation, and taxonomically implement our findings by (1) designating a lectotype for Paroedura bastardi, now restricted to the extreme South-East of Madagascar, (2) resurrecting of the binomen Paroedura guibeae Dixon & Kroll, 1974, which is applied to the species predominantly distributed in the South-West, and (3) describing a third species, Paroedura rennerae sp. nov., which has the northernmost distribution within the species complex.