In this work, we have systematically explored the crystal structures of LiAlO2 at high pressures using crystal structure prediction method in combination with the density functional theory calculations. Besides the reported α, β, γ, δ and ε-phases, here we propose a new monoclinic ζ-LiAlO2 (C2/m) structure, which becomes thermodynamically and dynamically stable above 27 GPa. It is found that the cation coordination number increases from 4 to 6 under compression. Consisting of the compact {LiO6} and {AlO6} octahedrons, the newly-discovered ζ-phase possesses a very high density. Further electronic calculations show that LiAlO2 is still an insulator up to 60 GPa, and its bandgap increases upon compression. The present study advances our understanding on the crystal structures and high-pressure phase transitions of LiAlO2 that may trigger applications in multiple areas of industry and provoke more related basic science research.