Cucolepis gen. n. is erected as monotypic for Cucolepis cincta sp. n., a new species of cyclophyllidean cestode of the family Paruterinidae. The new species is described from the squirrel cuckoo, Piaya cayana Lesson (Aves: Cuculiformes), taken from two localities in Paraguay in 1984 and 1985. This new genus is most similar to the genus Triaenorhina Spasskii et Shumilo, 1965 in terms of the hook morphology and large epiphyseal structures extending from both the handle and guard, but differs in several aspects of the strobilar morphology, such as the shape of the cirrus sac, genital atrium, uterus and paruterine organ. The strobilar morphology of the new genus strongly resembles that of the genus Francobona Georgiev et Kornyushin, 1994, especially the shape of the cirrus sac and genital atrium, yet Francobona spp. lack the developed epiphyseal structures observed in species of Cucolepis and Triaenorhina. Previous records and the nature of parasite-host associations between cuculiform birds and their cestode parasites are discussed.