Carbon-bearing solids, fluids, and melts in the Earth's deep interior may play an important role in the long-term carbon cycle. Here we apply synchrotron X-ray single crystal micro-diffraction techniques to identify and characterize the high-pressure polymorphs of dolomite. Dolomite-II, observed above 17 GPa, is triclinic, and its structure is topologically related to CaCO(3)-II. It transforms above 35 GPa to dolomite-III, also triclinic, which features carbon in [3 + 1] coordination at the highest pressures investigated (60 GPa). The structure is therefore representative of an intermediate between the low-pressure carbonates and the predicted ultra-high pressure carbonates, with carbon in tetrahedral coordination. Dolomite-III does not decompose up to the melting point (2,600 K at 43 GPa) and its thermodynamic stability demonstrates that this complex phase can transport carbon to depths of at least up to 1,700 km. Dolomite-III, therefore, is a likely occurring phase in areas containing recycled crustal slabs, which are more oxidized and Ca-enriched than the primitive lower mantle. Indeed, these phases may play an important role as carbon carriers in the whole mantle carbon cycling. As such, they are expected to participate in the fundamental petrological processes which, through carbon-bearing fluids and carbonate melts, will return carbon back to the Earth's surface.