Corals (Metazoa; Cnidaria; Anthozoa) have recently been shown to play host to a widespread and diverse group of intracellular symbionts of the phylum Apicomplexa. These symbionts, colloquially called ‘corallicolids’, are mostly known through molecular analyses, and no formal taxonomy has been proposed. Another apicomplexan, Gemmocystis cylindrus (described from the coral Dendrogyra cylindrus), may be related to corallicolids, but lacks molecular data. Here, we isolate and describe motile trophozoite (feeding) corallicolids cells using microscopic (light, SEM, and TEM) and molecular phylogenetic analysis to provide the basis for a formal description. Phylogenetic analyses using nuclear and plastid rRNA operons, and three mitochondrial protein sequences derived from single-cell transcriptomes, all confirm that these organisms fall into a discrete deep-branching clade within the Apicomplexa not closely related to any known species or major subgroup. As a result, we assign this clade to a new order, Corallicolida ord. nov., and family, Corallicolidae fam. nov. We describe a type species, Corallicola aquarius gen. nov. sp. nov. from its Rhodactis sp. host, and also describe a second species, Anthozoaphila gnarlus gen. nov. sp. nov., from the coral host Madracis mirabilis. Finally, we propose reassigning the incertae sedis taxon G. cylindrus from the order Agamococcidiorida to the Corallicolida, based on similarities in morphology and host localization to that of the corallicolids.