In-depth investigations of the long-time known Zintl phase NaTl revealed a phase transition of tetragonal NaTl-tI8 [I4(1)/amd; a = 5.2268(9) angstrom, c = 7.539(1) angstrom, V = 205.97(9) angstrom(3)] to Zintl's cubic NaTl-cF16 [Fd3m; a = 7.4697(6) angstrom, V = 416.79(5) angstrom(3)] between 351 and 355 K. This phase transformation was observed for NaTl prepared by two different synthetic routes including Zintl's original procedure. An excess of sodium applied during the synthesis in liquid ammonia also resulted in the formation of NaTl-tI8. DSC measurements suggest a first order phase transition. In addition to in-situ temperature dependent powder X-ray diffraction experiments, DSC measurements and solid-state NMR investigations, we also performed theoretical DOS and band structure calculations for the cubic and tetragonal phase, respectively. The results suggest Na-Tl interactions in the second coordination sphere being responsible for the observed tetragonal distortion of Zintl's cubic NaTl.