The potential energy surface of LiBH4 is investigated by a ground-state search method based on simulated annealing and first-principles density functional theory calculations. A new stable orthogonal structure with Pnma symmetry is found, which is 9.66 kJ/mol lower in energy than the proposed Pnma structure by Soulie et al. [J. Alloys Compd. 346, 200 (2002)]. For the high-temperature structure, we suggest a new monoclinic P2/c structure, which is 21.26 kJ/mol over the ground-state energy and shows no lattice instability.