Mitrostoma nototheniae Manter, 1954 is redescribed from Aplodactylus arctidens Richardson, off northern Tasmania. Opisthadena dimidia Linton, 1910 is reported from Kyphosus bigibbus Lacepède, Ningaloo, Western Australia, K. cinerascens (Forsskål), off Heron Island and Ningaloo, Western Australia, Kyphosus cornelii (Whitley), off Kalbarri, Western Australia, K. sydneyanus Günther, off Fremantle, Western Australia, K. sydneyanus ?, Ningaloo, Western Australia and K. vaigiensis (Quoy et Gaimard), off Heron and Lizard Islands, Queensland and Moorea, French Polynesia: measurements and an illustration are given. Neopisthadena habei Machida, 1980 is reported from K. sydneyanus off Fremantle, Western Australia: measurements and an illustration are given. Data derived from these specimens are used to recode a data-matrix developed by León-Règagnon et al. (1996), and the resultant tree produced is almost congruent with that of these authors. Our data indicate that this group of parasites is associated mostly with herbivorous hosts and that O. dimidia, while geographically widespread, is stenoxenic to the genus Kyphosus.