Novel superhard materials, especially those with superior thermal and chemical stability, are needed to replace diamond. Carbon nitrides (C-N), which are likely to possess these characteristics and have even been expected to be harder than diamond, are excellent candidates. Here we report three new superhard and thermodynamically stable carbon nitride phases. Based on a systematic evolutionary structure searches, we report a complete phase diagram of the C-N system at 0-300 GPa and analyze the hardest metastable structures. Surprisingly, we find that at zero pressure, the earlier proposed graphitic-C3N4 structure () is dynamically unstable, and we find the lowest-energy structure based on s-triazine unit and s-heptazine unit.