The monotypic Protorhinoxenus gen. n. is proposed to accommodate a species with the following characteristics: 1) tubular sclerotised vagina, 2) vaginal pore dextrolateral, 3) ventral and dorsal anchors with undifferentiated elongate shaft and base (representing approximately 2/3 of the length of anchor), and 4) superficial and deep roots of ventral and dorsal anchors lacking. Protorhinoxenus prochilodi sp. n. is described from the gills of Prochilodus lineatus (Valenciennes) of the Represa Capivari-Cachoeira, Municipality of Campina Grande do Sul, metropolitan area of Curitiba, Parana. Specimens of other probable new species of Protorhinoxenus are reported from Prochilodus lineatus of the Rio Paranapanema, Municipality of Salto Grande, Sao Paulo; Hoplias spp. of the Rio Dois de Fevereiro, Municipality of Antonina, Parana, and the Rio Piraquara, metropolitan area of Curitiba, Parana; Leporinus elongatus Valenciennes of the Rio Tibagi, Municipality of Jataizinho, Parana; and Schizodon fasciatum Agassiz of the Rio Solimoes, island of Marchantaria, near Manaus, Amazonas. Protorhinoxenus appears to be a sister group of Rhinoxenus Kritsky, Boeger et Thatcher, 1988 based on the following apparent synapomorphies: 1) ventral and dorsal anchors lacking superficial and deep roots, 2) ventral and dorsal anchors with elongate shaft, and 3) male copulatory organ with counterclockwise rings.