The synthesis, structure, and thermal stability of the periodate double perovskites A2NaIO6 (A= Ba, Sr, Ca) were investigated in the context of potential application for the immobilization of radioiodine. A combination of X-ray diffraction and neutron diffraction, Raman spectroscopy, and DFT simulations were applied to determine accurate crystal structures of these compounds and understand their relative stability. The compounds were found to exhibit rock-salt ordering of Na and I on the perovskite B-site; Ba2NaIO6 was found to adopt the Fm-3m aristotype structure, whereas Sr2NaIO6 and Ca2NaIO6 adopt the P21/n hettotype structure, characterized by cooperative octahedral tilting. DFT simulations determined the Fm-3m and P21/n structures of Ba2NaIO6 to be energetically degenerate at room temperature, whereas diffraction and spectroscopy data evidence only the presence of the Fm-3m phase at room temperature, which may imply an incipient phase transition for this compound. The periodate double perovskites were found to exhibit remarkable thermal stability, with Ba2NaIO6 only decomposing above 1050 °C in air, which is apparently the highest recorded decomposition temperature so far recorded for any iodine bearing compound. As such, these compounds offer some potential for application in the immobilization of iodine-129, from nuclear fuel reprocessing, with an iodine incorporation rate of 25-40 wt%. The synthesis of these compounds, elaborated here, is also compatible with both current conventional and future advanced processes for iodine recovery from the dissolver off-gas.