Haplotypes of eight phlebotomine species were characterized by cycle sequencing a mitochondrial (mt) DNA fragment (cytochrome b to NADH1) amplified from single sandflies by PCR. Phlebotomus (Phlebotomus) papatasi displayed little variation throughout its large geographical range. We conclude that this vector of Leishmania major suffered a population bottleneck late in the Pleistocene and then radiated out from the eastern Mediterranean subregion. There was no support for a recent domestic lineage of P. papatasi . The mtDNA molecular clock in phlebotomines (subgenera Phlebotomus and Larroussius ) was calibrated by reference to palaeogeographical events in Africa and the Mediterranean subregion. It fitted a pairwise nucleotide sequence divergence rate of 1.0–2.5% per million years. Co‐evolution of L. major , its Phlebotomus vectors and mammalian reservoirs is discussed.