Finding novel compounds with unusual crystal structures and physical properties is always an important goal for the materials and chemistry community. Pressure becomes attractive due to its unique ability to break down many fundamental rules by modifying the chemical properties of elements, overcoming reaction barriers and shortening interatomic distances, leading to the formation of some novel materials with unexpected properties. In this work, for the first time we have analyzed the high-pressure phase diagram, crystal structures and electron properties of the Mg-Br system up to 200 GPa using unbiased structure searching techniques. Besides the already known MgBr2, here we report that three unusual stoichiometries of Mg-Br compounds can be stabilized at high pressures as MgBr3, MgBr and Mg4Br. Firstly, among the predicted stable compounds, we find that the Mg4Br in the I4/mmm structure stabilized at 178 GPa behaves as a typical electride, indicating that the formation pressure of an electride for Mg can be significantly reduced by bonding with Br atoms. Secondly, it is surprising that the unexpected oxidation states of Br approaching -2 are observed in the predicted I4/mmm Mg4Br and Pm3[combining macron]m MgBr compounds. Furthermore, P21/m MgBr3 and I4[combining macron]2m MgBr3 phases are predicted as superconductors with an estimated Tc of 23.2 and 0.49 K, respectively. Our work represents a significant step toward understanding the high pressure behaviors of alkaline earth halides and searching for novel high temperature superconductors.