Two species of Coccomyxa Léger et Hesse, 1907, one of the least studied myxosporean genera, are reported from shallow coastal waters in the Gulf of Eilat, Red Sea, Israel. A new species, Coccomyxa jirilomi sp. n. is described from the spotted frillgoby Bathygobius cyclopterus (Valenciennes) (Gobiidae). It forms polysporous plasmodia that invade the liver and form packed clusters inside the bile ductules. Plasmodia also occur in the bile ducts and gall bladder of the host, attached to the epithelial lining or free floating in the bile. Infected hepatic bile ductules packed with plasmodia were partially occluded, with evidence of cholestasis, periductular fibrosis and pericholangitis. The mature spore is ellipsoid, has smooth valves and contains a single polar capsule with the polar filament arranged in 4-5 oblique coils. Spore dimensions are 9.0-11.3 × 5.0-7.0 µm. A second species, Coccomyxa sp., with smaller 7.6-9.6 × 4.2-5.2 µm and more delicate spores, was found in the gall bladder of the rippled rockskipper, Istiblennius edentulus (Forster et Schneider) (Blenniidae). The small subunit (SSU) rDNA sequence analysis of both Coccomyxa species suggests that they are closely related to members of the genera Myxidium, Zschokkella and Auerbachia, whose members infect the gall bladder of marine fish.