The sodium-iodine (Na-I) battery exhibits significant potential as an alternative energy storage device to the lithium-ion battery. However, its development is hindered by inadequate electrical and thermal stability, as well as the dissolution and shuttling of polyiodide. In this study, we report a preparation method for melamine carbon sponge (MC) via carbonizing a commercially available kitchen sponge. It was revealed that the as-prepared MC, composed of unique self-growing carbon nanotubes, could provide both physical and chemical adsorption capabilities for intermediate polyiodides to improve the electrochemical performance of NaI. Consequently, the NaI/MC electrode effectively minimized polyiodide dissolution and reduced the electrochemical impedance. The NaI/MC cathode demonstrated a high average discharge capacity of 92.75 mAh·g^–1 over 200 cycles while maintaining a coulombic efficiency of 94%. The research findings from our study have promising applications in Na-I batteries.