Gymnorhadinorhynchus gen. n. is proposed to accommodate its type species, G. decapteri sp. n., a parasite of the marine fish Decapterus punctatus (Cuvier), caught from the coastal waters of Brazil. Gymnorhadinorhynchus decapteri sp. n. was morphologically most similar to species of two echinorhynchid families, the Rhadinorhynchidae and the Cavisomidae, particularly in the structure of the proboscis and the absence of somatic spines, respectively. This combination of morphological features made it difficult to assign our specimen to an extant family of the Acanthocephala. Therefore, in order to clarify the systematic placement of G. decapteri, a molecular phylogenetic analysis was performed based on the SSU and LSU rDNA and the mitochondrial cox1 gene sequences obtained for the new taxon and other 26 acanthocephalan species. The results of parsimony and maximum likelihood analyses, using individual, combined and concatenated sequence data, consistently indicate that the specimens do not belong to any known family of the Echinorhynchida. Rather, G. decapteri represents a distinct lineage that is closely related to the Transvenidae, but distantly related to both the Rhadinorhynchidae and the Cavisomidae. Gymnorhadinorhynchidae fam. n. is therefore erected. This newly described family can be distinguished from other families of Echinorhynchida by the combination of the following morphological characters: a proboscis cylindrical with 10 rows of 22-26 hooks, dorsoventral differences in proboscis hooks, basal hooks forming a ring and being abruptly larger than anterior hooks, absence of trunk spines and presence of four tubular cement glands. This combination, in addition to several molecular autapomorphies, justifies the erection of a new genus, Gymnorhadinorhynchus gen. n., in order to accommodate this new species.