Background: The Greek island of Crete is endemic for both visceral leishmaniasis (VL) and recently increasing cutaneous leishmaniasis (CL). This study summarizes published data on the sand fly fauna of Crete, the results of new sand fly samplings and the description of a new sand fly species. Methods: All published and recent samplings were carried out using CDC light traps, sticky traps or mouth aspirators. The specific status of Phlebotomus (Adlerius) creticus n. sp., was assessed by morphological analysis, cytochrome b (cytb) sequencing and MALDI-TOF protein profiling. Results: Published data revealed the presence of 10 Phlebotomus spp. and 2 Sergentomyia spp. During presented field work, 608 specimens of 8 species of Phlebotomus and one species of Sergentomyia were collected. Both published data and present samplings revealed that the two most common and abundant species were Phlebotomus neglectus, a proven vector of Leishmania infantum causing VL, and Ph. similis, a suspected vector of L. tropica causing CL. In addition, the field surveys revealed the presence of a new species, Ph. (Adlerius) creticus n. sp. Conclusions: The identification of the newly described species is based on both molecular and morphological criteria, showing distinct characters of the male genitalia that differentiate it from related species of the subgenus Adlerius as well as species-specific sequence of cytb and protein spectra generated by MALDI-TOF mass spectrometry.