Members of the Psychrilyobacter spp. of the phylum Fusobacteria have been recently suggested to be amongst the most significant primary degraders of the detrital organic matter in sulfidic marine habitats, despite representing only a small proportion (<0.1%) of the microbial community. In this study, we have isolated a previously uncultured Psychrilyobacter species (strains SD5^T and BL5; Psychrilyobacter piezotolerans sp. nov.) from the sulfidic waters (i.e., 2000 m depth) of the Black Sea and investigated its physiology and genomic capability in order to better understand potential ecological adaptation strategies. P. piezotolerans utilized a broad range of organic substituents (carbohydrates and proteins) and, remarkably, grew at sulfide concentrations up to 32 mM. These flexible physiological properties were supported by the presence of the respective metabolic pathways in the genomes of both strains. Growth at varying hydrostatic pressure (0.1–50 MPa) was sustained by modifying its membrane lipid composition. Thus, we have isolated a novel member of the ‘rare biosphere’, which endures the extreme conditions and may play a significant role in the degradation of detrital organic matter sinking into the sulfidic waters of the Black Sea.