Two new species of Tereancistrum Kritsky, Thatcher & Kayton, 1980 are described from the gills of Prochilodus lineatus (Prochilodontidae) collected from the upper Paraná River floodplain, Brazil. T. toksonum n. sp. is characterised by a slim ventral bar with a sclerotised membrane along the anterior margin. Another characteristic is the dorsal anchor with an elongated deep root. T. curimba n. sp. is similar to T. ornatus Kritsky, Thatcher & Kayton, 1980 but possesses a sclerotised structure between the accessory sclerites of the ventral anchors. Moreover, the accessory anchor sclerites of this new species are longer than those described for T. ornatus.