In recent years there has been growing interest in analyzing the geographical variations between populations of different Phlebotomus spp. by comparing the sequences of various genes. However, little is known about the genetic structure of Phlebotomus ariasi. In this study, we were able to sequence a fragment of the mitochondrial Cyt b gene in 133 sandflies morphologically identified as P. ariasi and proceeding from a wide geographical range covering 35 locations in 11 different regions from five countries. The intra-specific diversity of P. ariasi is high, with 45 haplotypes differing from each other by one to 26 bases and they are distributed in two mitochondrial lineages, one limited geographically to Algeria and the other widely dispersed across Mediterranean countries. The Algerian lineage is characterized by having 13 fixed polymorphisms and is made up of one sole haplotype. The European/Moroccan P. ariasi lineage is characterized by being made up of a great diversity of haplotypes (44) which display some geographical structuring. This could be one of the multiple factors involved in the epidemiological heterogeneity of the foci of leishmaniasis. Phlebotomus chadlii is the sister group of European/Moroccan P. ariasi. The separation of the Algerian haplotype, H45, from the rest of the specimens, European/Moroccan P. ariasi and P. chadlii, is well supported by the bootstrap analysis.