Based on light and scanning electron microscopical studies, a new nematode parasite, Barracudia australiensis n. sp. (Philometridae), is described from the gall-bladder of the marine fish (obtuse barracuda) Sphyraena obtusata Cuvier (Sphyraenidae, Perciformes) from off the eastern Pacific coast of Australia, for which a new genus Barracudia n. g. is established. This new genus is mainly characterised by features found in the male: sickle-shaped, ventrally curved spicules, a gubernacum with a broad, dorsally bent distal portion and a markedly dorsoventrally elongated cloacal aperture. Based on these features, Barracudia spp. conspicuously differ from representatives of all other philometrid genera with known males. Philometra philippinensis Quiazon & Yoshinaga, 2013 is transferred to Barracudia as B. philippinensis (Quiazon & Yoshinaga, 2013) n. comb. Barracudia australiensis is the third nominal species of philometrids described from the Sphyraenidae and the 19th species of the Philometridae recorded from fishes in Australian waters.