It is well known that pressure causes profound changes in the properties of atoms and chemical bonding, leading to the formation of many unusual materials. Here we systematically explore all stable calcium carbides at pressures from ambient to 100 GPa using variable-composition evolutionary structure predictions using the USPEX code. We find that Ca5C2, Ca2C, Ca3C2, CaC, Ca2C3 and CaC2 have stability fields on the phase diagram. Among these, Ca2C and Ca2C3 are successfully synthesized for the first time via high-pressure experiments with excellent structural correspondence to theoretical predictions. Of particular significance is the base-centred monoclinic phase (space group C2/m) of Ca2C, a quasi-two-dimensional metal with layers of negatively charged calcium atoms, and the primitive monoclinic phase (space group P21/c) of CaC with zigzag C4 groups. Interestingly, strong interstitial charge localization is found in the structure of R-3m-Ca5C2 with semi-metallic behaviour.