Holothurian glycosaminoglycan (hGAG) is a high-molecular-weight form of fucosylated chondroitin sulfate and has an antithrombotic effect. Our previous studies demonstrated that hGAG efficiently inhibited tumor cell metastasis. The interplays between thrombosis and tumor progression may have a major impact on hematogenous metastasis. In this study, we demonstrated that the mouse melanoma B16F10 cells treated with hGAG displayed a significant reduction of metastasis and coagulation capacity in vitro and in vivo. Mechanistic studies revealed that hGAG treatment in B16F10 cells remarkably inhibited the formation of fibrin through attenuating the generation of activated Factor Xa (FXa), without affecting the expression of urokinase (uPA) and plasminogen activator inhibitor 1 (PAI-1) that involved in fibrinolysis. Moreover, hGAG treatment downregulated the transcription and protein expression of tissue factor (TF). Promoter deletions, site mutations and functional studies identified that the nuclear transcription factor NF-κB binding region is responsible for hGAG-induced inhibition of TF expression. While the hGAG treatment of B16F10 cells was unable to inhibit NF-κB expression and phosphorylation, hGAG significantly prevented nuclear translocation of NF-κB from the cytosol, a potential mechanism underlying the transcriptional suppression of TF. Moreover, hGAG markedly suppressed the activation of p38MAPK and ERK1/2 signaling pathways, the central regulators for the expression of metastasis-related matrix metalloproteinases (MMPs). Consequently, hGAG exerts a dual function in the inhibition of metastasis and coagulation activity in mouse melanoma B16F10 cells. Our studies suggest hGAG to be a promising therapeutic agent for metastatic cancer treatment.