The genus Culicoides includes vectors of important animal diseases such as bluetongue and Schmallenberg virus (BTV and SBV). This genus includes 1300 species classified in 32 subgenera and 38 unclassified species. However, the phylogenetic relationships between different subgenera of Culicoides have never been studied. Phylogenetic analyses of 42 species belonging to 12 subgenera and 8 ungrouped species of genus Culicoides from Ecuador, France, Gabon, Madagascar and Tunisia were carried out using two molecular markers (28S rDNA D1 and D2 domains and COI mtDNA). Sequences were subjected to non-probabilistic (maximum parsimony) and probabilistic (Bayesian inference (BI)) approaches. The subgenera Monoculicoides, Culicoides, Haematomyidium, Hoffmania, Remmia and Avaritia (including the main vectors of bluetongue disease) were monophyletic, whereas the subgenus Oecacta was paraphyletic. Our study validates the subgenus Remmia (= Schultzei group) as a valid subgenus, outside of the subgenus Oecacta. In Europe, Culicoides obsoletus, Culicoides scoticus and Culicoides chiopterus should be part of the Obsoletus complex whereas Culicoides dewulfi should be excluded from this complex. Our study suggests that the current Culicoides classification needs to be revisited with modern tools.