Carbon nitrides featuring three-dimensional frameworks of CN4 tetrahedra are one of the great aspirations of materials science, expected to have a hardness greater than or comparable to diamond. After more than three decades of efforts to synthesize them, no unambiguous evidence of their existence has been delivered. Here, the high-pressure high-temperature synthesis of three carbon-nitrogen compounds, tI14-C3N4, hP126-C3N4, and tI24-CN2, in laser-heated diamond anvil cells, is reported. Their structures are solved and refined using synchrotron single-crystal X-ray diffraction. Physical properties investigations show that these strongly covalently bonded materials, ultra-incompressible and superhard, also possess high energy density, piezoelectric, and photoluminescence properties. The novel carbon nitrides are unique among high-pressure materials, as being produced above 100 GPa they are recoverable in air at ambient conditions.