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.