A recent phylogenetic analysis of the Myxinidae based on the 16S rRNA gene resulted in synonymization of Paramyxine with Eptatretus. This created homonymy of Paramyxine fernholmi with Eptatretus fernholmi and Paramyxine wisneri with Eptatretus wisneri. In order to resolve this nomenclatural dilemma, we made a more extensive phylogenetic assessment of the Myxinidae and examined the nomenclature of the family. We used 75 sequences (37 of which new for this study) of a 561 bp fragment of the 16S rRNA gene, representing 33 species, and 72 sequences (37 of which new for this study) of a 687 bp fragment of the cytochrome c oxidase subunit I (COI) gene, representing 23 species, to reconstruct the phylogeny of Myxinidae. The monophyly of the subfamily Myxininae, traditionally characterized by having a single pair of external gill openings, was rejected (0.50 Bayesian posterior probability) by the 16S analysis, but supported by the COI and combined COI+16S analyses (0.99 and 0.81 Bpp, respectively). The monophyly of the subfamily Eptatretinae, characterized by having several pairs of external gill openings, was not supported by the 16S analysis and rejected by the COI and combined COI+16S analysis due to the placement of Eptatretus lopheliae as the earliest branch of Myxinidae (0.71 and 0.57 Bpp, respectively). Eptatretus lopheliae and Eptatretus rubicundus formed a monophyletic group and were allocated to a new genus, Rubicundus, characterized by the presence of an elongated tubular nostril and reddish coloration. A new monotypic subfamily, Rubicundinae, was proposed for Rubicundus. The synonymy of the genera Paramyxine and Quadratus with Eptatretus was confirmed. E. fernholmi is renamed Eptatretus luzonicus. Eptatretus wisneri was renamed Eptatretus bobwisneri. Petromyzon cirrhatus Forster, 1801, Homea banksii Fleming, 1822, and Bdellostoma forsteri Müller, 1836 are synonyms, but no type specimens are known to exist. Petromyzon cirrhatus was designated as type species of Eptatretus, conserving present usage. Gastrobranchus dombeyi Shaw, 1804 has priority over other names for Chilean myxinids. Bdellostoma stoutii was designated as type species of Polistotrema Gill. The validity of the Western Atlantic Myxine limosa as distinct from the Eastern Atlantic Myxine glutinosa was confirmed.