Environmental factors restrict the distribution of microbial eukaryotes but the exact boundaries for eukaryotic life are not known. Here, we examine protistan communities at the extremes of salinity and osmotic pressure, and report rich assemblages inhabiting Bannock and Discovery, two deep-sea superhaline anoxic basins in the Mediterranean. Using a rRNA-based approach, we detected 1,538 protistan rRNA gene sequences from water samples with total salinity ranging from 39 to 280 g/Kg, and obtained evidence that this DNA was endogenous to the extreme habitat sampled. Statistical analyses indicate that the discovered phylotypes represent only a fraction of species actually inhabiting both the brine and the brine-seawater interface, with as much as 82% of the actual richness missed by our survey. Jaccard indices (e.g., for a comparison of community membership) suggest that the brine/interface protistan communities are unique to Bannock and Discovery basins, and share little (0.8-2.8%) in species composition with overlying waters with typical marine salinity and oxygen tension. The protistan communities from the basins' brine and brine/seawater interface appear to be particularly enriched with dinoflagellates, ciliates and other alveolates, as well as fungi, and are conspicuously poor in stramenopiles. The uniqueness and diversity of brine and brine-interface protistan communities make them promising targets for protistan discovery.