We characterize a novel orthorhombic phase (gamma) of NaAlH4, discovered using first-principles molecular dynamics, and discuss its relevance to the dehydrogenation mechanism. This phase is close in energy to the known low-temperature structure and becomes the stabler phase above 320 K, thanks to a larger vibrational entropy associated with AlH4 rotational modes. The structural similarity of gamma-NaAlH4 to alpha-Na3AlH6 suggests it acts as a key intermediate during hydrogen release. Findings are consistent with recent experiments recording an unknown phase during dehydrogenation.