Calcium and magnesium carbonates are believed to be the host compounds for most of the oxidized carbon in the Earth's mantle. Here, using the evolutionary crystal structure prediction method uspex, we systematically explore the MgO-CO2 and CaO-CO2 systems at pressures ranging from 0 to 160 GPa to search for thermodynamically stable magnesium and calcium carbonates. While MgCO3 is the only stable magnesium carbonate, three calcium carbonates are stable under pressure: well-known CaCO3, and previously unknown Ca3CO5 and CaC2O5. Ca3CO5 polymorphs are found to contain isolated orthocarbonate CO44- tetrahedra, and are stable at relatively low pressures (>11GPa), whereas CaC2O5 is stable above 33 GPa and its polymorphs feature polymeric motifs made of CO4 tetrahedra. Detailed analysis of the chemical stability of CaCO3,Ca3CO5, and CaC2O5 in the environment typical of the Earth's lower mantle reveals that none of these compounds can exist in the Earth's lower mantle. Instead, MgCO3 is the main host of oxidized carbon throughout the lower mantle.