Phase separation is a ubiquitous process in seafloor hydrothermal vents, creating a large range of salinities. Toxic elements (e.g., arsenic) partition into the vapor phase, and thus can be enriched in both high and low salinity fluids. However, investigations of microbial diversity at sites associated with phase separation are rare. We evaluated prokaryotic diversity in arsenic-rich shallow-sea vents off Milos Island (Greece) by comparative analysis of 16S rRNA clone sequences from two vent sites with similar pH and temperature but marked differences in salinity. Clone sequences were also obtained for aioA-like functional genes (AFGs). Bacteria in the surface sediments (0–1.5 cm) at the high salinity site consisted of mainly Epsilonproteobacteria (Arcobacter sp.), which transitioned to almost exclusively Firmicutes (Bacillus sp.) at ~10 cm depth. However, the low salinity site consisted of Bacteroidetes (Flavobacteria) in the surface and Epsilonproteobacteria (Arcobacter sp.) at ~10 cm depth. Archaea in the high salinity surface sediments were dominated by the orders Archaeoglobales and Thermococcales, transitioning to Thermoproteales and Desulfurococcales (Staphylothermus sp.) in the deeper sediments. In contrast, the low salinity site was dominated by Thermoplasmatales in the surface and Thermoproteales at depth. Similarities in gas and redox chemistry suggest that salinity and/or arsenic concentrations may select for microbial communities that can tolerate these parameters. Many of the archaeal 16S rRNA sequences contained inserts, possibly introns, including members of the Euryarchaeota. Clones containing AFGs affiliated with either Alpha- or Betaproteobacteria, although most were only distantly related to published representatives. Most clones (89%) originated from the deeper layer of the low salinity, highest arsenic site. This is the only sample with overlap in 16S rRNA data, suggesting arsenotrophy as an important metabolism in similar environments.