Gastrointestinal myxosporean parasites from the genus Enteromyxum are known to cause severe disease, resulting in high mortalities in numerous species of cultured marine fishes globally. Originally described as Myxidium spp., they were transferred to a new genus, Enteromyxum, to emphasize their novel characteristics. Their retention in the family Myxidiidae at the time was warranted, but more comprehensive phylogenetic analyses have since demonstrated the need for a new family for these parasites. We discovered a novel Enteromyxum in wild fish from Malaysia and herein describe the fourth species in the genus and erect a new family, the Enteromyxidae n. fam., to accommodate them. Enteromyxum caesio n. sp. is described infecting the tissues of the stomach in the redbelly yellowtail fusilier, Caesio cuning, from Malaysia. The new species is distinct from all others in the genus, as the myxospores although morphologically similar, are significantly smaller in size. Furthermore, small subunit ribosomal DNA sequence data reveal that E. caesio is <84% similar to others in the genus, but collectively they form a robust and discrete clade, the Enteromyxidae n. fam., which is placed as a sister taxon to other histozoic marine myxosporeans. In addition, we describe, using transmission electron microscopy, the epicellular stages of Enteromyxum fugu and show a scanning electron micrograph of a mature myxospore of E. caesio detailing the otherwise indistinct sutural line, features of the polar capsules and spore valve ridges. The Enteromyxidae n. fam. is a commercially important group of parasites infecting the gastrointestinal tract of marine fishes and the histozoic species can cause the disease enteromyxosis in intensive finfish aquaculture facilities. Epicellular and sloughed histozoic stages are responsible for fish-to-fish transmission in net pen aquaculture systems but actinospores from an annelid host are thought to be necessary for transmission to fish in the wild.