Two new nematode species, Paragendria papuanensis sp. n. (Quimperiidae) and Rhabdochona papuanensis sp. n. (Rhabdochonidae), are described from the intestine of freshwater fishes Glossamia gjellerupi (Weber et Beaufort) (Apogonidae) and Melanotaenia affinis (Weber) (Melanotaeniidae), respectively, from the Sogeram River (Ramu River basin), Madang Province, northern Papua New Guinea. The former species is characterized mainly by the absence of oesophageal teeth, the presence of conspicuously inflated papillae of the last two subventral pairs, a gubernaculum, spicules 69-75 µm long, eggs measuring 57-66 × 39-45 µm, and by a small body (male and female 3.2-3.7 and 5.8 mm long, respectively). Paragendria is considered a valid genus, to which P. aori (Khan et Yaseen, 1969) comb. n., P. guptai (Gupta et Masoodi, 2000) comb. n., P. hanumanthai (Gupta et Jaiswal, 1988) comb. n. and P. vermae (Gupta et Masoodi, 2000) comb. n. are newly transferred. Rhabdochona papuanensis differs from all congeners mainly in having hammer-shaped deirids and from individual species also in other characters. Both findings represent the first records of species of Paragendria and Rhabdochona from the Australian zoogeographical region and the first records of the representatives of these genera from fishes of the families Apogonidae and Melanotaeniidae, respectively.