Nanotechnologies have been exploited to develop safe and effective medicines and pharmaceuticals. In the present study, a novel functional nanomedicine constructed from a bioactive polysaccharide and selenium nanoparticles (SeNPs) was developed. A highly-branched β-(1→3)-D-glucan (AF1) with high anti-tumor activity was used to self-assemble hollow nanofibers with an apparent average diameter of 92 nm; Se nanoparticles were synthesized via the reduction of sodium selenite. The results of light scattering, transmission electron microscopy, and X-ray diffraction demonstrated that the spherical SeNPs with a mean diameter of 46 nm were entrapped in the cavities of the AF1 hollow nanofibers through the formation of Se–O bonds between SeNPs and AF1, leading to the good dispersion and high stability in water for over 16 months. In vitro and in vivo assays indicated that the AF1-Se nanocomposite had higher anti-tumor activities against breast cancer. Furthermore, AF1-Se displayed a broad-spectrum inhibition against human cancers with low half maximal inhibitory concentration (IC₅₀) values and low toxicity to normal cells. Particularly, the inhibition ratio of AF1-Se against MCF-7 cancer cells reached 75% at a concentration of 200 μg·mL^–1 with 29 μM Se content, much higher than that by treatment with AF1 alone, suggesting a strong synergic effect and nano impact. Overall, we developed a method for increasing the stability, anti-tumor activity, and safety of SeNPs by wrapping with bioactive polysaccharides.