In spite of their potential as biologically active compounds, the high molecular mass and viscous natures of fucoidans have hampered their applications especially as a therapeutic agent. Herein the fucoidan-degrading enzyme activities were partially purified from the cultured cells of Sphingomonas paucimobilis PF-1 mainly by ammonium sulfate precipitation. This enzyme preparation degraded fucoidans from the Korean Undaria pinnatifida sporophyll into several low-molecular weight fuco-oligosaccharides (LMFOs) with less than 3,749 Da. The FTIR spectra of intact fucoidan and mixture of LMFOs (1,389~3,749 Da) showed no significant structural difference except for about 10% reduced level of sulfate esters in LMFOs. The LMFOs have exerted strong anticoagulating activities at which the activated partial thromboplastin time (APTT) and thrombin time (TT) were significantly prolonged, although 3~20 times weaker activities were observed than those of intact fucoidan. In addition, unlike intact fucoidan, LMFOs did not affect significantly to the prothrombin time (PT). These results suggest that the partially purified fucoidan-degrading enzyme preparation is valuable for the production of fuco-oligosaccharides having anticoagulating activities, and that the molecular weight and/or sulfate content of the fucoidan from the Korean Undaria pinnatifida sporophyll could be important factors for its anticoagulating activity.