Selenotetrelate compounds Na4TtSe4 (Tt = Si, Ge, Sn) were synthesized by solid-state reactions. A new modification of Na4SiSe4 (Na4SiSe4-cP72), which crystallizes in the cubic space group P4̅3n (no. 218) with a = 12.130(1) Å and V = 1784.453(5) Å3, and a new modification of Na4SnSe4 (Na4SnSe4-tI216), which crystallizes in the tetragonal space group I41/acd (no. 142) with a = 14.4053(4) Å, c = 28.5751(8) Å and V = 5929.7(3) Å3, were discovered. All of the title compounds exhibit moderate to good sodium ion conductivities, as revealed by electrochemical impedance spectroscopy. The formation reaction of Na4SiSe4 was further investigated by high-temperature X-ray powder diffraction of the ball-milled reaction mixture. Density functional-based quantum chemical calculations were performed to compare the different modifications of Na4SiSe4 and Na4SnSe4 energetically. Further modifications of Na4SiSe4 and Na4GeSe4 seem plausible, as revealed by density functional theory modeling. The stability of the hypothetic modifications was examined by phonon dispersion calculations.