Irradiated graphite waste management is one of the major challenges of nuclear power-plant decommissioning throughout the world and significantly in the UK, France and Russia where over 85 reactors employed graphite as moderator or core material. To date, the considerable volume (>300,000 tonnes worldwide) and heterogeneity of contamination observed in irradiated graphite, designates this material as higher activity waste, which resides predominately intact, at multiple reactor sites awaiting disposal in a deep or near-surface Geological Disposal Facility (GDF) yet to be built. This study presents a novel and non-destructive method for the treatment suitable for irradiated graphite materials, with the aim to remove contamination from corrosion and fission products and therefore downgrade the category of waste and enable accelerated disposal which does not require managed storage and disposal as intermediate level waste in a GDF . A novel electrochemical decontamination approach in a high-temperature molten salt medium was applied to irradiated UK Magnox grade graphite, fixed on the working electrode immersed in LiCl-KCl eutectic at 723 K. By selecting the appropriate value of the absolute magnitude of current and the number of transitions between positive and negative current, substantial removal of radionuclide contamination (60Co, 133Ba, 137Cs, 154Eu) from the graphite was achieved. Up to 80% reduction of total initial activity for 60Co was achieved without significant degradation of the graphite material (<7% mass loss). The magnitude of activity removed from the graphite was sufficient to reclassify the remaining graphite material from Intermediate Level Waste to Low Level Waste.