Non-metal nitrides are an exciting field of chemistry, featuring a significant number of compounds that can possess outstanding material properties. These properties mainly rely on maximizing the number of strong covalent bonds, with crosslinked XN6 octahedra frameworks being particularly attractive. In this study, the phosphorus-nitrogen system was studied up to 137 GPa in laser-heated diamond anvil cells, and three previously unobserved phases were synthesized and characterized by single-crystal X-ray diffraction, Raman spectroscopy measurements and density functional theory calculations. delta-P3N5 and PN2 were found to form at 72 and 134 GPa, respectively, and both feature dense 3D networks of the so far elusive PN6 units. The two compounds are ultra-incompressible, having a bulk modulus of K-0=322 GPa for delta-P3N5 and 339 GPa for PN2. Upon decompression below 7 GPa, delta-P3N5 undergoes a transformation into a novel alpha -P3N5 solid, stable at ambient conditions, that has a unique structure type based on PN4 tetrahedra. The formation of alpha -P3N5 underlines that a phase space otherwise inaccessible can be explored through materials formed under high pressure.