Paramyxida is an order of rhizarian protists that parasitise marine molluscs, annelids and crustaceans. They include notifiable pathogens (Marteilia spp.) of bivalves and other taxa of economic significance for shellfish production. The diversity of paramyxids is poorly known, particularly outside of commercially important hosts, and their phylogenetic position is unclear due to their extremely divergent 18S rDNA sequences. However, novel paramyxean lineages are increasingly being detected in a wide range of invertebrate hosts, and interest in the group is growing, marked by the first ‘Paramyxean Working Group’ Meeting held in Spain in February 2015. We review the diversity, host affiliations, and geographical ranges of all known paramyxids, present a comprehensive phylogeny of the order and clarify its taxonomy. Our phylogenetic analyses confirm the separate status of four genera: Paramarteilia, Marteilioides, Paramyxa and Marteilia. Further, as including M. granula in Marteilia would make the genus paraphyletic we suggest transferring this species to a new genus, Eomarteilia. We present sequence data for Paramyxa nephtys comb. n., a parasite of polychaete worms, providing morphological data for a clade of otherwise environmental sequences, sister to Marteilioides. Light and electron microscopy analyses show strong similarities with both Paramyxa and Paramyxoides, and we further discuss the validity of those two genera. We provide histological and electron microscopic data for Paramarteilia orchestiae, the type species of that genus originally described from the amphipod Orchestia; in situ hybridisation shows that Paramarteilia also infects crab species. We present, to our knowledge, the first known results of a paramyxid-specific environmental DNA survey of environmental (filtered water, sediment, etc.) and organismally-derived samples, revealing new lineages and showing that paramyxids are associated with a wider range of hosts and habitat types than previously known. On the basis of our new phylogeny we propose phylogenetic hypotheses for evolution of lifecycle and infectivity traits observed in different paramyxid genera.