We investigated the phylogenetic relationships within the Monticola rock-thrushes, an open-habitat genus inhabiting a large part of the Old World. Our results support one Oriental clade and one clade including African, Malagasy and Eurasian taxa. The biogeographic reconstruction obtained with the dispersal-vicariance analysis suggested Southern Africa plus Palearctic as the Monticola ancestral area. Our phylogenetic hypothesis suggests also some taxonomic changes. The polytypic Monticola solitarius includes two reciprocally monophyletic clades that should be recognized as full species, M. solitarius s.s. and M. philippensis. With the exclusion of the south-western population, M. imerinus, all other Malagasy rock-thrush populations should be merged in the monotypic, albeit polymorphic, M. sharpei. The genus Thamnolaea is shown to be non-monophyletic, with T. semirufa being part of the Monticola radiation, while T. cinnamomeiventris is related to other chat species inhabiting open-habitats. We demonstrate that a previous phylogenetic hypothesis for the rock-thrushes was flawed by the inclusion of contaminated sequences obtained from study-skins and we suggest some working guidelines to improve the reliability of the sequences obtained from old or degraded DNA.