  With the motivation of searching for new superconductors in the Mg-B system,
we performed ab initio evolutionary searches for all the stable compounds in
this binary system in the pressure range of 0-200 GPa. We found previously
unknown, yet thermodynamically stable, compositions MgB$_3$ and Mg$_3$B$_{10}$.
Experimentally known MgB$_2$ is stable in the entire pressure range 0-200 GPa,
while MgB$_7$ and MgB$_{12}$ are stable at pressures below 90 GPa and 35 GPa,
respectively. We predict a reentrant behavior for MgB$_4$, which becomes
unstable against decomposition into MgB$_2$ and MgB$_7$ at 4 GPa and then
becomes stable above 61 GPa. We find ubiquity of phases with boron sandwich
structures analogous to the AlB$_2$-type structure. However, with the exception
of MgB$_2$, all other magnesium borides have low electron-phonon coupling
constants $\lambda$ of 0.32 to 0.39 and are predicted to have T$_c$ below 3 K.
