An aerobic, Gram-negative bacterium, designated strain SD70T, was isolated from sea cucumber aquaculture farm sediment in Taean, Korea, and its taxonomic status was established by undertaking a polyphasic study. Cells of strain SD70T were non-motile, catalase-, and oxidase-positive, nonspore- forming, and horseshoe-shaped. Optimal growth was observed under 25–30°C, pH 7.0–8.0, and 3.0–5.0% (w/v) NaCl conditions. Phylogenetic analyses based on 16S rRNA gene sequences revealed that strain SD70T fell within an evolutionary group comprising species of the genus Cyclobacterium. Strain SD70T shared 92.1–98.5% 16S rRNA sequence similarity values with the type strains of species of the genus Cyclobacterium. Relatively low levels of DNA-DNA relatedness were found between strain SD70T and C. marinum DSM 745T (40.2%) and C. amurskyense KMM 6143T (15.8%). The predominant cellular fatty acids were iso-C15:0 (32.1%), and anteiso-C15:0 (9.1%). Menaquinone MK-7 was the only respiratory quinone. The G+C content of the genomic DNA was 36 mol%. The polar lipids were phosphatidylcholine, phosphatidylethanolamine, phosphatidylglycerol, and seven unidentified lipids. On the basis of phenotypic and genotypic data, strain SD70T represents a novel species of the genus Cyclobacterium, for which the name Cyclobacterium sediminis sp. nov. is proposed. An emended description of the genus Cyclobacterium is also provided.