Phlebotomine sand flies are the main natural vectors of Leishmania , which cause visceral and tegumentary tropical diseases worldwide. However, their taxonomy and evolutionary history remain poorly studied. Indeed, as for many human disease vectors, their small size is a challenge for morphological and molecular works. Here, we successfully amplified unbiased copies of whole genome to sequence thousands of restriction-site associated DNA (RAD) markers from single specimens of phlebotomines. RAD markers were used to infer a fully resolved phylogeny of the subgenus Paraphlebotomus (11 species + 5 outgroups, 32 specimens). The subgenus was not recovered as monophyletic and we describe a new subgenus Artemievus subg. nov. Depaquit for Phlebotomus alexandri . We also confirm the validity of Ph . riouxi which is reinstated as valid species. Our analyses suggest that Paraphlebotomus sensu nov . originated ca 12.9–8.5 Ma and was possibly largely distributed from peri-Mediterranean to Irano-Turranian regions. Its biogeographical history can be summarized into three phases: i) a first split between Ph . riouxi + Ph . chabaudi and other species that may have resulted from the rise of the Saharan belt ca 8.5 Ma; ii) a Messinian vicariant event (7.3–5.3 Ma) during which the prolonged drought could have resulted in the divergence of main lineages; iii) a recent radiation event (3–2 Ma) that correspond to cycles of wet and dry periods in the Middle East and the East African subregions during the Pleistocene. Interestingly these cycles are also hypothetical drivers of the diversification of rodents, in the burrows of which Paraphlebotomus larvae develop. By meeting the challenge of sequencing pangenomics markers from single, minute phlebotomines, this work opens new avenues for improving our understanding of the epidemiology of leishmaniases and possibly other human diseases transmitted by arthropod vectors. Author summary: Phlebotomine sand flies are tiny insects transmitting unicellular parasites called Leishmania worldwide. They are bad flyers and are known to be a group dispersing according to historical events. No invasive species are known within Phlebotomine sandflies. Their taxonomy includes about 40 genera. In the Old World, the subgenus Paraphlebotomus includes the main vectors of Leishmania tropica, the agent of a cutaneous leishmaniasis mostly in North Africa visceral and the Middle West. The goal of this study was to explore the phylogeny and the biogeographical history of this subgenus using a new generation sequencing technique. We successfully amplified DNA copies from the selected DNA extracts, some of them being more than 20 years old. We fully resolved the phylogeny of the subgenus Paraphlebotomus who was not recovered as monophyletic, meaning it does not include all the ascendants of last common ancestor. Consequently, the taxonomy was revised by the creation of a new subgenus and suggest that Paraphlebotomus originated about 10 million years ago. After a first split isolation North African species, the Messinian crisis caused by the aridification of the Tethys (the ancestor of the Mediterranean Sea) occurring 7 million years ago allowed the divergence of the main lineages including that of Phlebotomus sergenti the most important vector of the group. Most recent radiation events occurred during the Pleistocene. The historical biogeography of these Phlebotomine sandflies are closely related to that of the Leishmania they transmit.