Our survey of marine fish from South Africa and Indonesia revealed the presence of two new myxosporean species of the genus Sphaeromyxa for which we provide morphological and sequence data. Sphaeromyxa clini n. sp. detected in three Clinus spp. and Muraenoclinus dorsalis from South Africa is morphologically similar to Sphaeromyxa noblei previously described from Heteroclinus whiteleggii from Australia and to several other sphaeromyxids with arcuate spores and rounded ends. This similarity is reflected by phylogenetic positioning of S. clini n. sp. which clusters within the ‘incurvata’ group of the Sphaeromyxa clade. It differs from morphologically similar species by spore and polar capsule dimensions, host specificity and geographic distribution. Sphaeromyxa limocapitis n. sp., described from Gephyroberyx darwinii from Java, is morphologically similar to sphaeromyxids with straight spores and to marine Myxidium species with spindle-shaped spores but differs from them by spore and polar capsule dimensions, host specificity and geographic distribution. S. limocapitis n. sp. represents a separate lineage of the Sphaeromyxa clade and appears to be a missing link in the evolution of sphaeromyxids.