Polysaccharide is one of the necessary macromolecules in life activities, and it is also a very promising natural product for tumor prevention and treatment. In this study, two homogeneous polysaccharides (APS-4I and APS-4II) were isolated from Angelica sinensis (Oliv.) Diels. APS-4I was a linear glucan with molecular weight of 16.1 kDa, which was composed of 88.4% α-1,6-Glcp, 4.1% α-1,2-Glcp, 3.9% α-1,3-Glcp, and 2.8% α-T-Glcp. APS-4II was a novel polysaccharide with molecular weight of 11.1 kDa, which consisted of 55.4% α-1,6-Glcp, 10.4% α-1,3,5-Araf, 8.7% α-T-Araf, 9.2% α-1,5-Araf, 4.0% α-1,3-Araf, 3.6% α-1,4-Galp, and 9.1% β-1,3-Galp. NMR results demonstrated that APS-4II has a backbone composed of →6)-α-Glcp-(1 → 6)-α-Glcp-(1 → 5)-α-Araf-. (1 → 5)-α-Araf-(1 → 3,5)-α-Araf-(1 → 3)-β-Galp-(1 → 3)-β-Galp-(1 → 4)-α-Galp-(1 → 3)-α-Araf-(1 → 3,5)-α-Araf-(1→. Both APS-4I and APS-4II inhibited the tumor growth of B16-bearing mice, and the suppressive effect of APS-4II reached 64.7 ± 7.3%. Meanwhile, there were higher lymphocyte numbers and the levels of IL-2, IFN-γ, and TNF-α in peripheral blood of APS-4II-treated mice than those in APS-4I-treated mice. Furthermore, APS-4II showed a higher inhibitory effect on the proliferation of B16 cells and stronger promoting effects on the proliferation of splenocytes, the phagocytosis of peritoneal macrophages, and the cytotoxicity of NK cells. These results demonstrated that APS-4II could be a promising therapeutic agent for melanoma.