Fucoidan, a sulfated polysaccharide extracted from brown seaweeds, has been shown to possess various antioxidant, anticoagulant, antiviral, and anticancer functions. In this study, we focused on low molecular weight fucoidan (LMWF) which was extracted from New Zealand Undaria pinnatifida, and investigated its anti-proliferative effects, combined with a quadruplex-forming oligonucleotide aptamer (GroA, AS1411), a powerful cell surface Nucleolin inhibitor, in prostate cancer cells. We examined LMWF (<10 kDa) and compared it with laboratory grade Fucoidan purchased from Sigma (FS), all extracted from the same seaweed species U. pinnatifida. We found that LMWF significantly improved the anti-proliferative effect of GroA, as it decreased cancer cell growth and viability and increased cell death. This research may provide the foundation for LMWF to be used against prostate cancers as a supplement therapy in combination with other therapeutic agents.