Adults and plerocercoids of a new species of Heteronybelinia (Trypanorhyncha, Tentaculariidae) were recovered from the skate Sympterygia bonapartii (Rajiformes: Rajidae) and two species of teleosts, Raneya brasiliensis (Ophidiiformes: Ophidiidae) and Nemadactylus bergi (Perciformes: Cheilodactylidae), respectively. Heteronybelinia mattisi n. sp. differs from its congeners in its possession of a tentacular armature consisting of hooks with slight differences in size and shape on opposite surfaces of the tentacle (uncinate with rounded bases on the bothrial surface and uncinate with elongate bases on the antibothrial surface), without a characteristic basal armature, hooks increasing in size toward the tip of the tentacles, and pars bothrialis slightly overlapping with bulbs. The description of Heteronybelinia is emended regarding the distribution of testes to include species without postovarian testes (H. palliata and H. mattisi), and without testes anterior to cirrus sac on the poral side (H. robusta and H. mattisi). Host data are summarized for all 15 valid species of Heteronybelinia. Host specificity of adults and plerocercoids of Heteronybelinia is variable among species, the adults being more host specific than the plerocercoids. With the exception of H. mattisi, the definitive hosts of all species of Heteronybelinia for which adults are known include carcharhiniform sharks. Heteronybelinia mattisi seems to have oioxenous specificity for its definitive batoid host, S. bonapartii, and to be more specific for the intermediate hosts than most of its congeners.