Species of two monotypic genera, Ephedrocephalus Diesing, 1850 and Zygobothrium Diesing, 1850 (Cestoda: Proteocephalidae), parasites of one of the most basal members of the catfish family Pimelodidae, the redtail catfish, Phractocephalus hemioliopterus, in the Neotropical Region, are redescribed based on the evaluation of type specimens and newly collected material. Generic diagnoses are amended to provide a robust baseline for the future re-arrangement of the classification of proteocephalid cestodes. Ephedrocephalus is typified by the medullary position of the ovary and uterus, the cortical distribution of vitelline follicles (dispersed throughout almost the entire ventral cortex) and the testes in one dorsal field. Zygobothrium is primarily characterized by its possession of a robust scolex bearing four uniloculate suckers with two openings each and by the tetralobed velum (laciniations) on every proglottid (two on the ventral and two on the dorsal side). The redtail catfish is the definitive host of as many as seven species of proteocephalid cestodes, which, however, do not represent a monophyletic group. Some species, including Z. megacephalum, are among the earliest diverged parasites of Neotropical catfishes, being closely related to African and North American proteocephalids from catfishes, whereas others such as E. microcephalus belong to more recently diverged taxa with uncertain interrelations. Unlike most proteocephalids of the redtail catfish, which almost always infect the anterior parts of the host intestine, E. microcephalus and Z. megacephalum occur exclusively in its posterior third. A key to the identification of the proteocephalid species parasitizing P. hemioliopterus is also presented.