The prognosis of liver cancer was inferior among tumors. New medicine treatments are urgently needed. In this study, a novel exopolysaccharide EPS364 was purified from Vibrio alginolyticus 364 which was isolated from South China Sea cold seep. Further research suggested that EPS364 consisted of mannose, glucosamine, gluconic acid, galactosamine, arabinose with a molar ratio of 5:9:3.4:0.8:1.5. The molecular weight of EPS364 was 14.8 kDa. Our results further indicated that EPS364 was β-linked and phosphorylated polysaccharide. Notably, EPS364 exhibited significant anti-tumor activity. Besides, EPS364 induced Huh7.5 cells apoptosis, collapse of mitochondrial membrane potential (MMP) and generation of reactive oxygen species (ROS). Proteomic and quantitative real-time PCR analyses indicated that EPS364 blocked cancer cell adhesion and induced apoptosis via targeting FGF19–FGFR4 signaling pathway. These findings suggested that EPS364 was a promising anti-tumor agent for pharmacotherapy.