Phylogenetic relationships within the Orchideae sensu Pridgeon et al, remain one of the biggest unresolved issues in our understanding of the taxonomy of the orchids. Members of the Orchideae are numerous and widespread in Africa but remain poorly represented in phylogenetic research. In this study we included a broad sampling of African taxa for which we sequenced three plastid (rbcl, matK and trnL + trnL-F) and two nuclear regions (ITS and 18S). We used 368 sequences representing 278 species and 49 genera to infer relationships using the Bayesian Inference and Maximum Likelihood method. Our results show strong support for three clades, two of which almost entirely match the historical circumscription of Orchidinae and Habenariinae, and the third, Bartholininae, sister to the former two, includes the genera Holothrix and Bartholina. Stenoglottis should be assigned to Orchidinae and not to Habenariinae. Several genera such as Habenaria, Cynorkis and Benthamia are shown to be para- or polyphyletic: Bonatea, Centrostigma, Platycoryne and Roeperocharis are all embedded in Habenaria; Physoceras, Arnottia and part of Benthamia are embedded in Cynorkis. We propose a subdivision of Orchideae sensu lato into nine subtribes, but refrain from making generic re-arrangements until more extensive or more in-depth studies have been done.