The cichlid species flock of Lake Tanganyika is comprised of seven seeding lineages that evolved in step with changes of the lake environment. One seeding lineage diversified into at least six lineages within a short period of time. Our study focuses on the diversification of one of these lineages, the Ectodini, comprising highly specialized, sand- and rock-dwelling species. They display two distinct breeding styles: maternal and biparental mouthbrooding. By analyzing three mtDNA gene segments in 30 species representing all 13 described genera, we show that the Ectodini rapidly diversified into four clades at the onset of their radiation. The monotypic genus Grammatotria is likely to represent the most ancestral split, followed by the almost contemporary origin of three additional clades, the first comprising the benthic genus Callochromis, the second comprising the benthic genera Asprotilapia, Xenotilapia, Enantiopus, and Microdontochromis, and the third comprising the semi-pelagic genera Ophthalmotilapia, Cardiopharynx, Cyathopharynx, Ectodus, Aulonocranus, Lestradea, and Cunningtonia. Our study confirms the benthic and sand-dwelling life-style as ancestral. Rocky habitats were colonized independently in the Xenotilapia- and Ophthalmotilapia-clade. The Xenotilapia-clade comprises both maternal and biparental mouthbrooders. Their mode of breeding appears to be highly plastic: biparental mouthbrooding either evolved once in the common ancestor of the clade, to be reverted at least three times, or evolved at least five times independently from a maternally mouthbrooding ancestor. Furthermore, the genera Xenotilapia, Microdontochromis, Lestradea, and Ophthalmotilapia appeared paraphyletic in our analyses, suggesting the need of taxonomic revision.