Corals form diverse and valuable communities at all ocean depths. Unfortunately, they face a variety of threats, including increasing ocean temperatures, disease, and pollutants from human activities. But another less-expected threat may cause stress to ocean corals. Apicomplexans are a large group of parasites that cause major human diseases including malaria and toxoplasmosis. But these species don’t always live as human parasites – they also live among coral in tropical reefs. How the microbes can mitigate or exacerbate stress on coral communities, particularly those in deeper ocean environments, is unknown. A recent study evaluated the coral-residing microbes in deep-sea corals from the Gulf of Mexico. DNA sequencing identified 23 different types of apicomplexans, each with different patterns of niche and host. Some closely related microbes associated only with closely related corals, while others were present on a variety of coral types. The results indicate that apicomplexans can be found beyond shallow water, in deep-sea coral reefs, and the sequences obtained shed light on the evolutionary history of these important parasites.