High-pressure phases of NaAlH 4 are predicted using the ab initio evolutionary algorithm. our first-principles calculations reveal that the low-pressure I4 1/a phase containing AlH 4 tetrahedra transforms into the monoclinic P2 1/c phase at 3.8 GPa and then into the orthorhombic Ima2 phase at 20.5 GPa. The predicted two structures contain AlH 6 octahedra and AlH 7 decahedra, respectively. Coexistence of P2 1/c and Ima2 phases can explain better the measured x-ray diffraction patterns, transition pressure, and volume contraction. Our results provide a comprehensive understanding for the experimental findings.