We describe a new freshwater myxosporean species Ceratomyxa gracillima n. sp. from the gall bladder of the Amazonian catfish Brachyplatystoma rousseauxii; the first myxozoan recorded in this host. The new Ceratomyxa was described on the basis of its host, myxospore morphometry, ssrDNA and internal transcribed spacer region (ITS-1) sequences. Infected fish were sampled from geographically distant localities: the Tapajós River, Pará State, the Amazon River, Amapá State and the Solimões River, Amazonas State. Immature and mature plasmodia were slender, tapered at both ends, and exhibited vermiform motility. The ribosomal sequences from parasite isolates from the three localities were identical, and distinct from all other Ceratomyxa sequences. No population-level genetic variation was observed, even in the typically more variable ITS-1 region. This absence of genetic variation in widely separated parasite samples suggests high gene flow as a result of panmixia in the parasite populations. Maximum likelihood and maximum parsimony analyses placed C. gracillima n. sp. sister to Ceratomyxa vermiformis in a subclade together with Ceratomyxa brasiliensis and Ceratomyxa amazonensis, all of which have Amazonian hosts. This subclade, together with other Ceratomyxa from freshwater hosts, formed an apparently early diverging lineage. The Amazonian freshwater Ceratomyxa species may represent a radiation that originated during marine incursions into the Amazon basin that introduced an ancestral lineage in the late Oligocene or early Miocene.