Fucoidan, a polysaccharide containing abundant fucose and sulfate ester group, was prepared from Laminaria japonica. In order to obtain fucoidan-degrading enzyme, bacteria capable of degrading fucoidan were screened from kelp. A bacterial strain named RC2-3 was obtained, which degraded fucoidan by the maximum extent of 54% ± 1.3%, the highest among all bacterial isolates. High-performance size exclusion chromatography (HPSEC) showed that the molecular weight of fucoidan was gradually reduced by RC2-3 with culturing time, suggesting the production of fucoidan-degrading enzyme by RC2-3. Phylogenetic analysis of partial 16S ribosomal RNA gene (16S rDNA) sequence showed that RC2-3 belonged to the family Flavobacteriaceae. However, it showed different physiological and biochemical characteristics from the known Flavobacteriaceae members producing fucoidan-degrading enzyme, thus RC2-3 was proposed to be a new member of this family.