The Nycteribiidae is a group of ectoparasitic and hematophagous flies associated with bats and barely known in Colombia. The revision of previously collected material and additional fieldwork through various regions in Colombia let us to identify various fly species and their associated bats. Particularly, this is the first record of the species Basilia tiptoni Guimarães, 1966, for Colombia, collected on the bat Gardnerycteris keenani (Handley, 1960) (Mammalia: Chiroptera), from the Antioquia and Sucre departments. Additionally, and as a new geographic and host record, the species Basilia ferrisi Schuurmans Stekhoven, Jr., 1931 was found on the bat Eptesicus brasiliensis (Desmarest, 1819) from the Sucre department.