Background: The aim of this study is to describe the major evolutionary historical events among Leishmania, sandflies, and the associated animal reservoirs in detail, in accordance with the geographical evolution of the Earth, which has not been previously discussed on a large scale. Methodology and Principal Findings Leishmania and sandfly classification has always been a controversial matter, and the increasing number of species currently described further complicates this issue. Despite several hypotheses on the origin, evolution, and distribution of Leishmania and sandflies in the Old and New World, no consistent agreement exists regarding dissemination of the actors that play roles in leishmaniasis. For this purpose, we present here three centuries of research on sandflies and Leishmania descriptions, as well as a complete description of Leishmania and sandfly fossils and the emergence date of each Leishmania and sandfly group during different geographical periods, from 550 million years ago until now. We discuss critically the different approaches that were used for Leishmana and sandfly classification and their synonymies, proposing an updated classification for each species of Leishmania and sandfly. We update information on the current distribution and dispersion of different species of Leishmania (53), sandflies (more than 800 at genus or subgenus level), and animal reservoirs in each of the following geographical ecozones: Palearctic, Nearctic, Neotropic, Afrotropical, Oriental, Malagasy, and Australian. We propose an updated list of the potential and proven sandfly vectors for each Leishmania species in the Old and New World. Finally, we address a classical question about digenetic Leishmania evolution: which was the first host, a vertebrate or an invertebrate? Conclusions and Significance: We propose an updated view of events that have played important roles in the geographical dispersion of sandflies, in relation to both the Leishmania species they transmit and the animal reservoirs of the parasites.