Dolomite is one of the major mineral forms in which carbon is subducted into the Earth’s mantle. End-member CaMg(CO3)2 dolomite typically breaks down upon compression into two carbonates at 5–6 GPa in the temperature range of 800–1200 K (Shirasaka et al. 2002). However, high-pressure X-ray diffraction experiments have shown that dense high-pressure polymorphs of dolomite may be favored over single-cation carbonates (Santillán et al. 2003; Mao et al. 2011; Merlini et al. 2012). Here we compare calculated dolomite structures to experimentally observed phases. Using density functional theory interfaced with a genetic algorithm that predicts crystal structures (USPEX), a monoclinic phase with space group C2/c was found to have lower energy at pressures above 15 GPa than all previously reported dolomite structures. It is possible that this phase is not observed experimentally due to a large activation energy of transition from dolomite I, resulting in the observed second-order phase transition to a metastable dolomite II. Due to the complex energy landscape for candidate high-pressure dolomite structures, several structurally unique metastable polymorphs exist. We calculate the equation of state of a set of lowest-energy dolomite polymorphs with space groups P1, P2/c, and C2/c up to 80 GPa. Our results demonstrate a need for calculations and experiments on Fe-Mn bearing high-pressure carbonate phases to extend our understanding of Earth’s deep carbon cycle and test whether high-pressure polymorphs of double-cation carbonates represent the main reservoir for carbon storage within downwelling regions of Earth’s mantle.