The sediment microbiota of the Mediterranean deep-sea anoxic hypersaline basins (DHABs) are understudied relative to communities in the brines and halocline waters. In this study, the active fraction of the prokaryotic community in the halocline sediments of L' Atalante, Urania, and Discovery DHABs was investigated based on extracted total RNA and 454 pyrosequencing of the 16S rRNA gene. Bacterial and archaeal communities were different in the sediments underlying the halocline waters of the three habitats, reflecting the unique chemical settings of each basin. The relative abundance of unique operational taxonomic units (OTUs) was also different between deep-sea control sediments and sediments underlying DHAB haloclines, suggesting adaptation to the steep DHAB chemical gradients. Only a few OTUs were affiliated to known bacterial halophilic and/or anaerobic groups. Many OTUs, including some of the dominant ones, were related to aerobic taxa. Archaea were detected only in few halocline samples, with lower OTU richness relative to Bacteria, and were dominated by taxa associated with methane cycling. This study suggests that, while metabolically active prokaryotic communities appear to be present in sediments underlying the three DHABs investigated, their diversity and activity are likely to be more reduced in sediments underlying the brines.