The members of the genus Heterixalus constitute one of the endemic frog radiations in Madagascar. Here we present a complete species-level phylogeny based on DNA sequences (4876 base pairs) of three nuclear and four mitochondrial markers to clarify the phylogenetic relationships among and within all known species of this genus, as well as the phylogenetic position of the monospecific Seychellean Tachycnemis seychellensis. Although the performance to resolve supported clades of Heterixalus species differed among the investigated gene fragments when analyzed separately, we could identify five well-supported species groups within Heterixalus in the combined analysis of all gene fragments. Our data strongly support a Heterixalus-Tachycnemis clade, and indicate the probable monophyly of Heterixalus placed sister to Tachycnemis. However, the diversification of these lineages may have happened in a short interval of time, leading to an unstable placement of Tachycnemis in the single-gene fragment phylogenies. Referring to the hitherto existing classification of Heterixalus, which is predominantly based on chromatic and bioacoustic characters, we examined the relative performance of these data sets relative to our molecular phylogeny. A Bayesian tree reconstructed with a bioacoustic data set yielded a higher resemblance to the molecular phylogeny than a tree constructed using a chromatic data set, which supports the importance of bioacoustic characters for systematic analyses of these anurans.