Through a systematic structural search we found an allotrope of carbon with Cmmm symmetry which we predict to be more stable than graphite for pressures above 10 GPa. This material, which we refer to as Z-carbon, is formed by pure sp(3) bonds and it provides an explanation to several features in experimental x-ray diffraction and Raman spectra of graphite under pressure. The transition from graphite to Z-carbon can occur through simple sliding and buckling of graphene sheets. Our calculations predict that Z-carbon is a transparent wide band-gap semiconductor with a hardness comparable to diamond.