We report a novel phase of carbon possessing a monoclinic C2/m structure (8atoms/cell) identified using an ab initio evolutionary structural search. This polymorph, which we call M-carbon, is related to the (2×1) reconstruction of the (111) surface of diamond and can also be viewed as a distorted (through sliding and buckling of the sheets) form of graphite. It is stable over cold-compressed graphite above 13.4 GPa. The simulated x-ray diffraction pattern and near K-edge spectroscopy are in satisfactory agreement with the experimental data on overcompressed graphite. The hardness and bulk modulus of this new carbon polymorph are calculated to be 83.1 and 431.2 GPa, respectively, which are comparable to those of diamond.