High salt concentrations, absence of light, anoxia, and high hydrostatic pressure make deep hypersaline anoxic basins (DHABs) in the Eastern Mediterranean Sea one of the most polyextreme habitats on Earth. Taking advantage of the unique chemical characteristics of these basins, we tested the effect of environmental selection and geographic distance on the structure of protistan communities. Terminal restriction fragment length polymorphism (T-RFLP) analyses were performed on water samples from the brines and seawater/brine interfaces of five basins: Discovery, Urania, Thetis, Tyro, and Medee. Using statistical analyses, we calculated the partitioning of diversity among the ten individual terminal restriction fragment (T-RF) profiles, based on peak abundance and peak incidence. While a significant distance effect on spatial protistan patterns was not detected, hydrochemical gradients emerged as strong dispersal barriers that likely lead to environmental selection in the DHAB protistan plankton communities. We identified sodium, magnesium, sulfate, and oxygen playing in concerto as dominant environmental drivers for the structuring of protistan plankton communities in the Eastern Mediterranean DHABs.