Fucoidan, a mixture of sulfated fucose-containing polysaccharides, was prepared from the algal bodies of Cladosiphon okamuranus (class Phaeophyceae, order Chordariales, family Chordariaceae) with a yield of 2.0% of the wet weight of the alga. To obtain enzymes that digest the fucoidan, we screened bacteria in the guy contents of the sea cucumber Stichopus japonicus for their ability to decrease the fucoidan in their culture media, and successfully isolated one bacterial strain that could decrease it. The bacterial strain was gram-negative and possessed menaquinone 7 as the predominant respiratory quinone, and the GC content of its genomic DNA was 52%. The results of the phylogenetic analysis of its 16S ribosomal DNA sequence indicated that the bacterial strain was a member of the division "Verrucomicrobia." However, as the bacterial strain is phylogenetically and phenotypically distinct from verrucomicrobial species described previously, the strain was assumed to be a new member of the division "Verrucomicrobia." When the bacterial strain was cultivated in an algal fucoidan-containing medium, the strain decreased fucoidan from C. okamuranus (44%), Nemacystus decipiens (19%), Laminaria japonica (31%), Kjellmaniella crassifolia (23%), sporophyl of Undaria pinnatifida (22%), Fucus vesiculosus (42%), and Ascophyllum nodosum (61%).