The cophyline microhylid frogs of Madagascar show a wide range of habitat specialization, ranging from terrestrial/burrowing and semi-arboreal to entirely arboreal species. The classification of these frogs is thus far mainly based upon morphological, largely osteological, characters that might be homoplastic. Using 1173 bp of DNA sequences from the mitochondrial 12S and 16S rRNA genes, we here present a molecular phylogeny for 28 species of all known genera, except for the genus Madecassophryne. The resulting maximum likelihood tree contained four major clades: one represented by the genus Anodonthyla, the second by Cophyla and Platypelis, the third by several terrestrial and semi-arboreal species of the genus Plethodontohyla, and the fourth by species of the genera Stumpffia, Plethodontohyla, and Rhombophryne. The results confirm that several cophyline lineages adapted independently to similar habitats, with multiple shifts among terrestriality and arboreality. The direction of these shifts cannot be ascertained due to unclarified relationships among the most basal lineages, but for one terrestrial species (Anodonthyla montana), it is most parsimonious to assume that it evolved from arboreal ancestors. Our results suggest that the genus Plethodontohyla is probably paraphyletic, and that the classification of this and of the genus Rhombophryne needs to be re-assessed.