Gills of carangid fishes in Australian waters are dominated by a diversity of polyopisthocotylean monogeneans. This study updates current knowledge of polyopisthocotyleans from carangid hosts in waters along the Queensland coast of Australia and also off New Caledonia. The discovery of Protomicrocotyle celebesensis Yamaguti, 1953 is the first record for the genus in Australian waters and represents a new geographic location for the species, extending its distribution from Sulawesi, Indonesia and Hawaii to Australia. Furthermore, Caranx ignobilis and Carangoides fulvoguttatus are reported as new host records for P. celebesensis. Carangoides gymnostethus is recorded as a new host for Heteromicrocotyla australiensis Rohde, 1977 from a new geographic location, namely Lizard Island, Queensland. Heteromicrocotyloides mirabilis Rohde, 1977 is reported from the gills of C. fulvoguttatus off Lizard Island, Queensland representing a new geographic record. Heteromicrocotyloides megaspinosus sp. nov. is described from the gills of C. fulvoguttatus from Lizard Island, Queensland and New Caledonia. The new species is distinguished from H. mirabilis by the larger number and size of spines in the male genital corona. Gonoplasius carangis was collected from Pseudocaranx dentex at Heron Island, Queensland. Gonoplasius longirostri is synonymised with G. carangis due to overlap in measurements and similar morphology. The number of 'dorsal pits' in this taxon may not be a useful character because they can be cryptic and hard to see. Most hosts from which these two Gonoplasius species have been collected previously have been synonymised as Pseudocaranx dentex except Caranx ascensionis which is now considered to be C. lugubris. Our report of G. carangis from P. dentex at Heron Island, Queensland is a new geographic record.