New tetragonal phases of crystalline carbon nitride (CN) and their atomic structures have been identified using a self-consistent-charge density-functional tight-binding method. A tetragonal rocksalt structure provides theoretical support to recent experimental evidence for a stoichiometric CN phase with tetragonal symmetry. A body-centered tetragonal CN phase with 1:1 stoichiometry is predicted to be highly stable and of interesting atomic structure with complicated C-C and N-N dimerizations along the c axis. The cubic-to-tetragonal transitions are carefully examined to understand the underlying mechanism.