Sulfated fucans, the complex polysaccharides, exhibit various biological activities. Herein, we purified two fucans from the sea cucumbers Holothuria edulis and Ludwigothurea grisea. Their structures were verified by means of HPGPC, FT-IR, GC–MS and NMR. As a result, a novel structural motif for this type of polymers is reported. The fucans have a unique structure composed of a central core of regular (1→2) and (1→3)-linked tetrasaccharide repeating units. Approximately 50% of the units from L. grisea (100% for H. edulis fucan) contain sides of oligosaccharides formed by nonsulfated fucose units linked to the O-4 position of the central core. Anticoagulant activity assays indicate that the sea cucumber fucans strongly inhibit human blood clotting through the intrinsic pathways of the coagulation cascade. Moreover, the mechanism of anticoagulant action of the fucans is selective inhibition of thrombin activity by heparin cofactor II. The distinctive tetrasaccharide repeating units contribute to the anticoagulant action. Additionally, unlike the fucans from marine alga, although the sea cucumber fucans have great molecular weights and affluent sulfates, they do not induce platelet aggregation. Overall, our results may be helpful in understanding the structure-function relationships of the well-defined polysaccharides from invertebrate as new types of safer anticoagulants.