Culicoides obsoletus is an abundant and widely distributed Holarctic biting midge species, involved in the transmission of bluetongue virus (BTV) and Schmallenberg virus (SBV) to wild and domestic ruminants. Females of this vector species are often reported jointly with two morphologically very close species, C. scoticus and C. montanus, forming the Obsoletus/Scoticus Complex. Recently, cryptic diversity within C. obsoletus was reported in geographically distant sites. Clear delineation of species and characterization of genetic variability is mandatory to revise their taxonomic status and assess the vector role of each taxonomic entity. Our objectives were to characterize and map the cryptic diversity within the Obsoletus/Scoticus Complex. Portion of the cox1 mitochondrial gene of 3763 individuals belonging to the Obsoletus/Scoticus Complex was sequenced. Populations from 20 countries along a Palaearctic Mediterranean transect covering Scandinavia to Canary islands (North to South) and Canary islands to Turkey (West to East) were included. Genetic diversity based on cox1 barcoding was supported by 16S rDNA mitochondrial gene sequences and a gene coding for ribosomal 28S rDNA. Species delimitation using a multi-marker methodology was used to revise the current taxonomic scheme of the Obsoletus/Scoticus Complex. Our analysis showed the existence of three phylogenetic clades (C. obsoletus clade O2, C. obsoletus clade dark and one not yet named and identified) within C. obsoletus. These analyses also revealed two intra-specific clades within C. scoticus and raised questions about the taxonomic status of C. montanus. To our knowledge, our study provides the first genetic characterization of the Obsoletus/Scoticus Complex on a large geographical scale and allows a revision of the current taxonomic classification for an important group of vector species of livestock viruses in the Palaearctic region.