Oxygen-depleted water columns (ODWCs) host a diverse community of eukaryotic protists that change dramatically in composition over the oxic-anoxic gradient. In the permanently anoxic Cariaco Basin, peaks in eukaryotic diversity occurred in layers where dark microbial activity (chemoautotrophy and heterotrophy) were highest, suggesting a link between prokaryotic activity and trophic associations with protists. Using 18S rRNA gene sequencing, parasites and especially the obligate parasitic clade, Syndiniales, appear to be particularly abundant, suggesting parasitism is an important, but overlooked interaction in ODWC food webs. Syndiniales were also associated with certain prokaryotic groups that are often found in ODWCs, including Marinimicrobia and Marine Group II archaea, evocative of feedbacks between parasitic infection events, release of organic matter, and prokaryotic assimilative activity. In a network analysis that included all three domains of life, bacterial and archaeal taxa were putative bottleneck and hub species, while a large proportion of edges were connected to eukaryotic nodes. Inclusion of parasites resulted in a more complex network with longer path lengths between members. Together, these results suggest that protists, and especially protistan parasites, play an important role in maintaining microbial food web complexity, particularly in ODWCs, where protist diversity and microbial productivity are high, but energy resources are limited relative to euphotic waters.