Treatment and immobilization of technetium-99 (99Tc) contained in reprocessed nuclear waste and present in contaminated subsurface systems represents a major environmental challenge. One potential approach to managing this highly mobile and long-lived radionuclide is immobilization into micro- and meso-porous crystalline solids, specifically sodalite. We synthesized and characterized the structure of perrhenate sodalite, Na8[AlSiO4]6(ReO4)2, and the structure of a mixed guest perrhenate/pertechnetate sodalite, Na8[AlSiO4]6(ReO4)2-x(TcO4)x. Perrhenate was used as a chemical analogue for pertechnetate. Bulk analyses of each solid confirm a cubic sodalite-type structure (P4̅3n, No. 218 space group) with rhenium and technetium in the 7+ oxidation state. High-resolution nanometer scale characterization measurements provide first-of-a-kind evidence that the ReO4- anions are distributed in a periodic array in the sample, nanoscale clustering is not observed, and the ReO4- anion occupies the center of the sodalite β-cage in Na8[AlSiO4]6(ReO4)2. We also demonstrate, for the first time, that the TcO4- anion can be incorporated into the sodalite structure. Lastly, thermochemistry measurements for the perrhenate sodalite were used to estimate the thermochemistry of pertechnetate sodalite based on a relationship between ionic potential and the enthalpy and Gibbs free energy of formation for previously measured oxyanion-bearing feldspathoid phases. The results collected in this study suggest that micro- and mesoporous crystalline solids maybe viable candidates for the treatment and immobilization of 99Tc present in reprocessed nuclear waste streams and contaminated subsurface environments.