Mg2Pb occurs in the cubic fluorite structure and is a semimetal with a band structure strongly affected by spin-orbit interaction on the Pb p states. Its properties are therefore of interest in the context of topological materials. In addition a different phase of Mg2Pb was experimentally reported, but its crystal structure and properties remain unknown. Here we determine the structure of this phase using ab initio evolutionary methods and report its properties. The energy of one tetragonal phase, space group P4/nmm, is 2 meV per atom higher than that of the ground state structure supporting the experimental observation. We find this tetragonal phase to be a compenstated anisotropic metal with strong spin orbit effects. Many other metastable structures have also been identified, especially one orthorhombic structure, space group Pnma, of which energy is 17 meV per atom higher than that of ground state structure and which perhaps could be the phase that was reported based on similarity of lattice parameters.