Phylogenetic relationships of Culicoides species of the Afrotropical region are problematic as different authors disagree on the placement of species into specific subgenera or groups. In this study we sequenced two mitochondrial (COI and 16S rDNA) and two nuclear (CAD and 28S rDNA) gene fragments to reconstruct phylogenetic relationships within the Avaritia, Remmia and Synhelea subgenera and the Milnei, Neavei and Similis groups of Culicoides using both Bayesian inference and maximum-likelihood approaches. Based on phylogenetic trees, we used the bGMYC (Bayesian General Mixed Yule Coalescent model) and the PTP (Bayesian Poisson Tree Processes) to investigate species boundaries. All species relationships within the studied subgenera and groups were well-supported by using morphological characters and molecular analyses. The subgenus Avaritia includes (i) all of the species of the Imicola group, as well as the putative new species, C. sp. 22, and we confirmed the monophyly of this group; (ii) the Dasyops group includes C. kanagai and C. sp. 54 Meiswinkel (new species), shown to be monophyletic; (iii) the C. sp. #20 belongs to the Orientalis group; (iv) C. grahamii, C. gulbenkiani and C. kibatiensis. Our results also show that subgenus Remmia is monophyletic. Relationships of species of the Milnei group were well-supported and demonstrate the monophyly of this group. Borkent's classification for Similis group is confirmed. In addition, C. neavei and C. ovalis (Neavei group) are placed in the subgenus Synhelea.