The energy landscape of Mg(BH(4))(2) under pressure is explored by ab initio evolutionary calculations. Two new tetragonal structures, with space groups P4 and I4(1)/acd, are predicted to be lower in enthalpy by 15.4 and 21.2 kJ/mol, respectively, than the earlier proposed P4(2)nm phase. We have simulated x-ray diffraction spectra, lattice dynamics, and equations of state of these phases. The density, volume contraction, bulk modulus, and simulated x-ray diffraction patterns of I4(1)/acd and P4 structures are in excellent agreement with the experimental results.