State of the art variable composition structure prediction based on density functional theory demonstrates that two new stoichiometries of PN, PN3 and PN2, become viable at high pressure. PN3 has a skutterudite-like Immm structure and is metastable with positive phonon frequencies at pressures between 10 and 100 GPa. PN3 is metallic and is the first reported nitrogen-based skutterudite. Its metallicity arises from nitrogen p-states which delocalise across N4 rings characteristic of skutterudites, and it becomes a good electron-phonon superconductor at 10 GPa, with a Tc of around 18 K. The superconductivity arises from strongly enhanced electron-phonon coupling at lower pressures, originating primarily from soft collective P-N phonon modes. The PN2 phase is an insulator with P2/m symmetry and is stable at pressures in excess of 200 GPa.