Choerodonicola Cribb, 2005 is a minor genus of opecoelid trematodes defined for species with exceptionally small eggs but otherwise generalised morphology. Four species are currently recognised, all from fishes collected in Japanese waters but each from different perciform families: a labrid, a scarid, a sparid and pinguipeds. We report on a new species, Choerodonicola arothokoros n. sp., from the blue-barred parrotfish Scarus ghobban Forsskål (Scaridae) collected in subtropical waters of Moreton Bay, south-east Queensland, Australia. Using genetic sequence data for the ITS2 rDNA marker, we matched adult C. arothokoros to intramollsucan stages discovered in an intertidal gastropod Herpetopoma atratum (Gmelin) (Vetigastropoda: Chilodontidae) collected in close proximity to the fish hosts. Notably, the cercariae lack a penetration stylet and are among the smallest known in the Opecoelidae. We provide the first assessment of the phylogenetic position of Choerodonicola based on sequence data generated for the phylogenetically informative 18S and 28S rRNA coding regions, for C. arothokoros and also C. renko Machida, 2014, which we recollected from the yellowback seabream Dentex hypselosomus Bleeker from the fish market in Minabe, Wakayama Prefecture, Japan. In our analyses, species of Choerodonicola resolved to neither of the major marine Plagioporinae (sensu lato) clades, clustering instead with Trilobovarium parvvatis Martin, Cutmore & Cribb, 2017, Podocotyloides parupenei (Manter, 1963) Pritchard, 1966 and Macvicaria magellanica Laskowski, Jeżewski & Zdzitowiecki, 2013. This clade is phylogenetically distinctive such that it has the potential to be recognised as a new opecoelid subfamily, but further investigation is required to establish the bounds for such a grouping and to determine the morphological and/or life-history patterns reflected by the phylogeny. Finally, we propose C. interruptus (Manter 1954) n. comb. for a species previously recognised in Plagioporus Stafford, 1904 and known only from Pseudolabrus miles (Schneider & Forster), a labrid endemic to New Zealand.