Agamococcidians are enigmatic and poorly studied parasites of marine invertebrates with unexplored diversity and unclear relationships to other sporozoans such as the human pathogens Plasmodium and Toxoplasma. It is believed that agamococcidians are not capable of sexual reproduction, which is essential for life cycle completion in all well studied parasitic apicomplexans. Here, we describe three new species of agamococcidians belonging to the genus Rhytidocystis. We examined their cell morphology and ultrastructure, resolved their phylogenetic position by using near-complete rRNA operon sequences, and searched for genes associated with meiosis and oocyst wall formation in two rhytidocystid transcriptomes. Phylogenetic analyses consistently recovered rhytidocystids as basal coccidiomorphs and away from the corallicolids, demonstrating that the order Agamococcidiorida Levine, 1979 is polyphyletic. Light and transmission electron microscopy revealed that the development of rhytidocystids begins inside the gut epithelial cells, a characteristic which links them specifically with other coccidiomorphs to the exclusion of gregarines and suggests that intracellular invasion evolved early in the coccidiomorphs. We propose a new superorder Eococcidia for early coccidiomorphs. Transcriptomic analysis demonstrated that both the meiotic machinery and oocyst wall proteins are preserved in rhytidocystids. The conservation of meiotic genes and ultrastructural similarity of rhytidocystid trophozoites to macrogamonts of true coccidians point to an undescribed, cryptic sexual process in the group.