A mesophilic, hydrogenotrophic methanogen, strain S3FaT, was isolated from sediments collected by Ocean Researcher I cruise ORI-934 in 2010 near the submarine mud volcano MV4 located at the upper slope of south-west Taiwan. The methanogenic substrates utilized by strain S3FaT were formate and H2/CO2 but not acetate, secondary alcohols, methylamines, methanol or ethanol. Cells of strain S3FaT were non-motile, irregular cocci, 0.5–1.0 μm in diameter. The surface-layer protein showed an Mr of 128 000.The optimum growth conditions were 37 °C, pH 7.1 and 0.17 M NaCl. The DNA G+C content of the genome of strain S3FaT was 62.3 mol %. Phylogenetic analysis revealed that strain S3FaT was most closely related to Methanoculleus marisnigri JR1T (99.3 % 16S rRNA gene sequence similarity). Genome relatedness between strain S3FaT and Methanoculleus marisnigri JR1T was computed using both genome-to-genome distance analysis (GGDA) and average nucleotide identity (ANI) with values of 46.3–55.5 % and 93.08 %, respectively. Based on morphological, phenotypic, phylogenetic and genomic relatedness data, it is evident that strain S3FaT represents a novel species of the genus Methanoculleus, for which the name Methanoculleus sediminis sp. nov. is proposed. The type strain is S3FaT ( = BCRC AR10044T = DSM 29354T).