A total of 4,840 phlebotomine sand flies from 54 localities in Putumayo department (=state), in the Colombian Amazon region, were collected in Shannon traps, CDC light traps, resting places and from human baits. At least 42 Lutzomyia species were registered for the first time to the department. Psychodopygus and Nyssomyia were the subgenera with the greatest number of taxa, the most common species being L. (N.) yuilli and L. (N.) pajoti. They were sympatric in a wide zone of Putumayo, indicating that they should be treated as full species (new status). Among the anthropophilic sand flies, L. gomezi and L. yuilli were found in intradomiciliar, peridomestic, urban or forest habitats. L. richardwardi, L. claustrei, L. nocticola and L. micropyga are reported for the first time in the Colombian Amazon basin. L. pajoti, L. sipani and L. yucumensis are new records for Colombia.