Efficient remediation of liquid radioactive waste, produced as in research and medicine, is crucial for increasing safety during the necessary storage of this material. A novel bio-magnetic nano-composite sorbent based on a natural product (Karaya gum) and magnetite nanoparticles was tested for the efficient removal of radioactive phosphorus 32P from liquid radioactive waste. This non-toxic nano-composite is well-suited to be used as a nano-hydrogel for storage of radioisotopes on a smaller space and without the risk of spills inherent to the initial liquid material. The maximum adsorption capacity of the nanocomposite synthesized in this study was found to be over 15 GBq/g. We present a thorough morphological characterization of the novel synthesized bio-magnetic nano-composite, as well as discuss the possible phosphorus adsorption mechanisms.