Four new species of fleas are described: Aphropsylla truncata sp. n. (Ethiopia), Ectinorus hirsutus sp. n. (Peru), Rhinolophopsylla traubi sp. n. (Angola), and Thaumapsylla wilsoni sp. n. (Papua New Guinea). Our understanding of the genus Aphropsylla is deficient, therefore a discussion of host/parasite relationships and new records from Uganda are provided. A key is provided for the genus Aphropsylla, while representatives of the other three genera are associated with existing keys to facilitate their identification. The presence of lucodiscs on Apropsylla and other genera is briefly discussed. The occurrence of lucodiscs among representatives of the order Siphonaptera deserves further investigation.