In Colombia, nine species of parasites of the genus Leishmania circulate in more than 20 sand fly species, putting at risk of contracting the disease approximately 60% of the population. The Federico Lleras Acosta Dermatological Center, a reference center in Colombia, has been treating patients with cutaneous and mucosal leishmaniasis for more than 15 years, identifying the infecting Leishmania species from different clinical samples, and recording systematically all the epidemiological and geographic information related to each diagnosed patient. With this valuable information, the objective of this work was to perform a long term and large-scale study, aiming to identify the Leishmania species circulating in Colombia from clinical samples from 1999 to 2016, and to assess their current and potential spatial distribution. In all, four Leishmania species were identified in 688 samples from 183 municipalities distributed in 28 of the 32 departments of the country, and 387 records were georeferenced, from 20 departments. The most widespread species was L. (V.) braziliensis, showing new collection records, and the species related to areas with highest leishmaniasis transmission was L. (V.) panamensis. Ecological niche models were built for the three species that had more than 20 georeferenced records, showing a potential distribution for L. (V.) braziliensis on 42% of the national territory mainly in the interandean valleys, and the Orinoquia and Amazon regions. Leishmania (V.) guyanensis potential distribution covers 36% of Colombia continental territory with a spatial distribution similar to that of L. (V.) braziliensis. There was a marked tendency of L. (V.) panamensis to be distributed in the northwest of the country occupying 35% of the national area and mainly in areas of transformed ecosystems. Species were identified in patients from areas where the occurrence of cases was unprecedented, which suggests that the distribution of Leishmania may be greater than currently known. To improve the predictive capacity of the models, we suggest incorporating, in future studies, Leishmania samples from vectors and reservoirs that have a greater dependence on environmental variables. Our results are an important tool for health systems because they allow potential areas of transmission and information gaps to be identified.