An ab initio variable-cell-shape molecular-dynamics algorithm is used to investigate the stability of three carbon nitrides with composition C3N4. The hexagonal β-C3N4 structure, which has been the subject of earlier investigations, is refined and its metastability is verified. Two other metastable structures are identified: a structure resembling zinc-blende CN with one C vacancy per cubic cell and a structure resembling graphitic CN with one C vacancy per four N sites. Both the refined β phase and the cubic phase have compressibilities comparable to that of diamond. The graphitic and the β phases lie very close in energy and are slightly favored over the cubic phase.