We provide molecular data (cox1, 18S rDNA and 28S rDNA) for 17 acanthocephalan species and 20 host-parasite combinations from Australian marine teleosts collected from off Queensland, Australia. Fourteen of these acanthocephalans are characterised with molecular data for the first time and we provide the first molecular data for a species of each of the genera Heterosentis Van Cleave, 1931, Pyriproboscis Amin, Abdullah & Mhaisen, 2003 and Sclerocollum Schmidt & Paperna, 1978. Using 18S and 28S rDNA sequences, the phylogenetic position of each newly sequenced species is assessed with both single-gene and concatenated 18S+28S maximum likelihood and Bayesian inference analyses. Additional phylogenetic analyses focusing on the genus Rhadinorhynchus Lühe, 1912 and related lineages are included. Our phylogenetic results are broadly consistent with previous analyses, recovering previously identified inconsistencies but also providing new insights and necessitating taxonomic action. We do not find sufficient evidence to recognise the Gymnorhadinorhynchidae Braicovich, Lanfranchi, Farber, Marvaldi, Luque & Timi, 2014 as distinct from the Rhadinorhynchidae Lühe, 1912. The family Gymnorhadinorhynchidae and its sole genus, Gymnorhadinorhynchus Braicovich, Lanfranchi, Farber, Marvaldi, Luque & Timi, 2014, are here recognised as junior synonyms of Rhadinorhynchidae and Rhadinorhynchus, respectively. The two species currently assigned to Gymnorhadinorhynchus are recombined as Rhadinorhynchus decapteri (Braicovich, Lanfranchi, Farber, Marvaldi, Luque & Timi, 2014) n. comb. and Rhadinorhynchus mariserpentis (Steinauer, Garcia-Vedrenne, Weinstein & Kuris, 2019) n. comb. In all of our analyses, Rhadinorhynchus biformis Smales, 2014 is found basal to the Rhadinorhynchidae + Transvenidae Pichelin & Cribb, 2001, thus resulting in a paraphyletic Rhadinorhynchidae. It appears that R. biformis may require a new genus and family; however, morphological data for this species are currently insufficient to adequately distinguish it from related lineages, thus we defer the proposal of any new higher-rank names for this species. Species of the genus Sclerocollum, currently assigned to the Cavisomidae Meyer, 1932, are found nested within the family Transvenidae. We transfer the genus Sclerocollum to the Transvenidae and amend the diagnosis of the family accordingly. The genera Gorgorhynchoides Cable & Linderoth, 1963 and Serrasentis Van Cleave, 1923, currently assigned to the Rhadinorhynchidae, are supported as sister taxa and form a clade in the Polymorphida. We transfer these genera and Golvanorhynchus Noronha, Fabio & Pinto, 1978 to an emended concept of the Isthomosacanthidae Smales, 2012 and transfer this family to the Polymorphida. Lastly, Pyriproboscis heronensis (Pichelin, 1997) Amin, Abdullah & Mhaisen, 2003, currently assigned to the Pomphorhynchidae Yamaguti, 1939, falls under the Polymorphida in our analyses with some support for a sister relationship with the Centrorhynchidae Van Cleave, 1916. As this species clearly does not belong in the Pomphorhynchidae and is morphologically and molecularly distinct from the lineages of the Polymorphida, we propose the Pyriprobosicidae n. fam. to accommodate it.