Symbioses between Bacteria, Archaea, and Eukarya in deep-sea marine environments represent a means for eukaryotes to exploit otherwise inhospitable habitats. Such symbioses are abundant in many low-oxygen benthic marine environments, where the majority of microbial eukaryotes contain prokaryotic symbionts. Here, we present evidence suggesting that in certain oxygen-depleted marine water-column habitats, the majority of microbial eukaryotes are also associated with prokaryotic cells. Ciliates (protists) associated with bacteria were found to be the dominant eukaryotic morphotype in the haloclines of two different deep-sea hypersaline anoxic basins (DHABs) in the Eastern Mediterranean Sea. These findings are compared to associations between ciliates and bacteria documented from the permanently anoxic waters of the Cariaco Basin (Caribbean Sea). The dominance of ciliates exhibiting epibiotic bacteria across three different oxygen-depleted marine water column habitats suggests that such partnerships confer a fitness advantage for ciliates in these environments.