CaFe₂O₄-type sodium postspinels (Na-CFs), with Na⁺ occupying tunnel sites, are of interest as prospective battery electrodes. While many compounds of this structure type require high-pressure synthesis, several compounds are known to form at ambient pressure. Here we report a large expansion of the known Na-CF phase space at ambient pressure, having successfully synthesized NaCrTiO₄, NaRhTiO₄, NaCrSnO₄, NaInSnO₄, NaMg_0.5Ti_1.5O₄, NaFe_0.5Ti_1.5O₄, NaMg_0.5Sn_1.5O₄, NaMn_0.5Sn_1.5O₄, NaFe_0.5Sn_1.5O₄, NaCo_0.5Sn_1.5O₄, NaNi_0.5Sn_1.5O₄, NaCu_0.5Sn_1.5O₄, NaZn_0.5Sn_1.5O₄, NaCd_0.5Sn_1.5O₄, NaSc_1.5Sb_0.5O₄, Na_1.16In_1.18Sb_0.66O₄, and several solid solutions. In contrast to earlier reports, even cations that are strongly Jahn-Teller active (e.g., Mn³⁺ and Cu²⁺) can form Na-CFs at ambient pressure when combined with Sn⁴⁺ rather than with the smaller Ti⁴⁺. Order and disorder are probed at the average and local length-scales with synchrotron powder X-ray diffraction and solid-state NMR spectroscopy. Strong ordering of framework cations between the two framework sites is not observed, except in the case of Na_1.16In_1.18Sb_0.66O₄. This compound is the first example of an Na-CF that contains Na⁺ in both the tunnel and framework sites, reminiscent of Li-rich spinels. Trends in the thermodynamic stability of the new compounds are explained on the basis of crystal-chemistry and density functional theory (DFT). Further DFT calculations examine the relative stability of the CF versus spinel structures at various degrees of sodium extraction in the context of electrochemical battery reactions.