Understanding the demographic history and genetic make-up of colonizing species is critical for inferring population sources and colonization routes. This is of main interest for designing accurate control measures in areas newly colonized by vector species of economically important pathogens. The biting midge Culicoides imicola is a major vector of orbiviruses to livestock. Historically, the distribution of this species was limited to the Afrotropical region. Entomological surveys first revealed the presence of C. imicola in the south of the Mediterranean basin by the 1970s. Following recurrent reports of massive bluetongue outbreaks since the 1990s, the presence of the species was confirmed in northern areas. In this study, we addressed the chronology and processes of C. imicola colonization in the Mediterranean basin. We characterized the genetic structure of its populations across Mediterranean and African regions using both mitochondrial and nuclear markers, and combined phylogeographical analyses with population genetics and approximate Bayesian computation. We found a west/east genetic differentiation between populations, occurring both within Africa and within the Mediterranean basin. We demonstrated that three of these groups had experienced demographic expansions in the Pleistocene, probably because of climate changes during this period. Finally, we showed that C. imicola could have colonized the Mediterranean basin in the Late Pleistocene or Early Holocene through a single event of introduction; however, we cannot exclude the hypothesis involving two routes of colonization. Thus, the recent bluetongue outbreaks are not linked to C. imicola colonization event, but rather to biological changes in the vector or the virus.