We used ab initio random structure searching (AIRSS) to investigate polymorphism in C3N4 carbon nitride as a function of pressure. Our calculations reveal new framework structures, including a particularly stable chiral polymorph of space group P43212 containing mixed sp2 and sp3-bonding, that we have produced experimentally and recovered to ambient conditions. As pressure is increased a sequence of structures with fully sp3-bonded C atoms and three-fold coordinated N atoms is predicted, culminating in a dense Pnma phase above 250 GPa. Beyond 650 GPa we find that C3N4 becomes unstable to decomposition into diamond and pyrite-structured CN2.