Some of the most extreme marine habitats known are the Mediterranean Deep Hypersaline Anoxic Basins (DHABs; water depth ~3500m). Brines of DHABs are nearly saturated with salt, leading many to suspect they are uninhabitable for eukaryotes. While diverse bacterial and protistan communities are reported from some DHAB water-column haloclines and brines, the existence and activity of benthic DHAB protists have rarely been explored. Here, we report findings regarding protists and fungi recovered from sediments of three DHAB (Discovery, Urania, L’Atalante) haloclines, and compare these to communities from sediments underlying normoxic waters of typical Mediterranean salinity. Halocline sediments, where the redoxcline impinges the seafloor, were studied from all three DHABs. Microscopic cell counts suggested that halocline sediments supported denser protist populations than those in adjacent control sediments. Pyrosequencing analysis based on ribosomal RNA detected eukaryotic ribotypes in the halocline sediments from each of the three DHABs, most of which were fungi. Sequences affiliated with Ustilaginomycotina Basidiomycota were the most abundant eukaryotic signatures detected. Benthic communities in these DHABs appeared to differ, as expected, due to differing brine chemistries. Microscopy indicated that only a low proportion of protists appeared to bear associated putative symbionts. In a considerable number of cases, when prokaryotes were associated with a protist, DAPI staining did not reveal presence of any nuclei, suggesting that at least some protists were carcasses inhabited by prokaryotic scavengers.