A bacterial strain FXJ8.089(T) was isolated from deep-sea water collected from the southwest Indian Ocean (49° 39' E 37° 47' S) at a depth of 2800 m, and its taxonomic position was investigated by a polyphasic approach. Phylogenetic analysis based on 16S rRNA gene sequences showed that strain FXJ8.089(T) belonged to the genus Cellulomonas and had the highest similarities with Cellulomonas oligotrophica (96.9 %) and Cellulomonas aerilata (96.6 %). It contained MK-9(H4) as the predominant menaquinone. The polar lipids were diphosphatidylglycerol and phosphatidylinositol mannosides. The cell-wall peptidoglycan type was A4β with an interpeptide bridge L-Orn-D-Glu. The cell-wall sugars were glucose, mannose and ribose. The DNA G+C content was 70.3 mol%. The strain also showed a number of physiological and biochemical characteristics that were distinct from the closely related species. Based on phenotypic and genotypic data, strain FXJ8.089(T) (= CGMCC 4.6945(T) = DSM 24960(T)) represents a novel species of the genus Cellulomonas, for which the name Cellulomonas marina sp. nov. is proposed.