Sodium-ion batteries have emerged as the most promising alternative to lithium-ion batteries due to the advantages of high natural abundance, low cost, environmental friendliness, and retention of charge capacity at low temperatures. However, novel anode and cathode materials need to be developed. In this work, Sandia octahedral molecular sieves – a class of ion exchangers with the general formula, Na2Nb2−xMIVxO6−x(OH)x·H2O (M = Ti, Zr; x = 0.04–0.40) – are introduced as novel anode materials for sodium-ion battery applications. In this study, sodium niobium titanium oxide, Na2Nb1.6Ti0.4O5.6(OH)0.4·H2O (Na-NTO), is prepared by a simple hydrothermal method, followed by exchange of the Na+ ion in the SOMS structure by one of the eleven selected divalent or monovalent cations, after which the electrochemical properties of the ion-exchanged SOMS materials are investigated and compared with those of the unexchanged SOMS material. Exchanging sodium for divalent zinc delivered an enhanced specific capacity (196 mAh g−1 at 10 mA g−1vs. 89 mAh g−1 for Na-NTO) at every current density, whereas exchange for cadmium delivered a high capacity retention of 72% at 50 mA g−1 after 100 cycles. The enhanced electrochemical performance is related to their lower ionic radii (compared to Na+), higher selectivity, optimal pore size and higher Na+-ion diffusion coefficient. While the performances of the materials investigated here are comparatively low, the present work provides an in-depth study of the effect of partial ion-replacement on electrochemical performance.