First-principles calculations of the relative stability, structure, and physical properties of carbon nitride polymorphs predict a cubic form of C3N4 with a zero-pressure bulk modulus exceeding that of diamond. Like diamond, this new phase could potentially be synthesized at high pressure and quenched to ambient pressure for use as a superhard material. The calculations also predict that alpha-C3N4 and graphite-C3N4 are energetically favored relative to beta-C3N4 and that published diffraction data can be re-indexed as alpha-C3N4 with lower error.