Species of the genus Leishmania (Kinetoplastida, Trypanosomatidae) are causative agents of leishmaniasis, a complex disease with variable clinical spectrum and epidemiological diversity, constituting, in some countries, a serious public health problem. The origin and evolution of leishmaniasis has been under discussion regarding some clinical and parasitological aspects. After the introduction of paleoparasitology, molecular methods and immunodiagnostic techniques have been applied allowing the recovery of parasite remains, as well as the diagnosis of past infections in humans and other hosts. The dating of archaeological samples has allowed the parasitological analysis in time and space. This manuscript presents the state of the art of leishmaniasis and prospects related to paleoparasitology studies and their contribution to the evolutionary and phylogenetic clarification of parasites belonging to the genus Leishmania, and the leishmaniasis caused by them.