Cystacanths of 4 species of Acanthocephala are reported for the first time from various species of fish belonging to the Order Pleuronectiformes from waters of the western Gulf of Carpentaria and the central coast of Queensland, Australia: Corynosoma cetaceum Johnston and Best, 1942 (Family Polymorphidae), Serrasentis cf. Sagittifer (Linton, 1889) and Rhadinorhynchus sp. (Family Rhadinorhynchidae), and Gorgorhynchoides sp. (Family Isthmosacanthidae). Approximately 32% of the 515 individual fish belonging to 24 species were infected with at least 1 cystacanth. Serrasentis cf. Sagittifer was the most-commonly encountered, infecting a total of 18 species of fish across both regions. Gorgorhynchoides sp. Infected 7 fish species in the Gulf of Carpentaria only while Rhadinorhynchus sp. (1 fish species) and C. cetaceum (7 fish species) were only found on the central coast of Queensland. Most fish were infected with a single cystacanth of any species. There was no relationship between total length of fish and intensity of infection for any species. This paper provides information on parasite infections in fish hosts commonly caught as by-catch and outlines the need for further studies on these fish to be able to determine sustainability of such fish stocks.