African cichlids formerly referred to as ”Tilapia” represent a paraphyletic species assemblage belonging to the so called haplotilapiine lineage which gave rise to the spectacular East African cichlid radiations (EARs) as well as to globally important aquaculture species. We present a comprehensive molecular phylogeny of representative haplotilapiine cichlids, combining in one data set four mitochondrial and five nuclear loci for 76 species, and compare it with phylogenetic information of a second data set of 378 mitochondrial ND2 haplotypes representing almost all important “Tilapia” or Tilapia-related lineages as well as most EAR lineages. The monophyly of haplotilapiines is supported, as is the nested sister group relationship of Etia and mouthbrooding tilapiines with the remaining haplotilapiines. The latter are consistently placed in eight monophyletic clades over all datasets and analyses, but several dichotomous phylogenetic relationships appear compromised by cytonuclear discordant phylogenetic signal. Based on these results as well as on extensive morphological evidence we propose a novel generic and suprageneric classification including a (re-)diagnosis of 20 haplotilapiine cichlid genera and nine tribes. New tribes are provided for the former subgenera Coptodon Gervais, 1853, HeterotilapiaRegan, 1920 and PelmatolapiaThys van den Audenaerde, 1969, in addition for “Tilapia” joka, Tilapia sensu stricto and Chilochromis, Etia, Steatocranus sensu stricto, the mouthbrooding tilapiines and for a clade of West African tilapiines.