Rotational excitation of interstellar PN molecules induced by collisions with H2 is investigated. We present the first ab initio four-dimensional potential energy surface (PES) for the PN-H2 van der Waals system. The PES was obtained using an explicitly correlated coupled cluster approach with single, double, and perturbative triple excitations [CCSD(T)-F12b]. The method of interpolating moving least squares was used to construct an analytical PES from these data. The equilibrium structure of the complex was found to be linear, with H2 aligned at the N end of the PN molecule, at an intermolecular separation of 4.2 Å. The corresponding well-depth is 224.3 cm-1. The dissociation energies were found to be 40.19 cm-1 and 75.05 cm-1 for complexes of PN with ortho-H2 and para-H2, respectively. Integral cross sections for rotational excitation in PN-H2 collisions were calculated using the new PES and were found to be strongly dependent on the rotational level of the H2 molecule. These new collisional data will be crucial to improve the estimation of PN abundance in the interstellar medium from observational spectra.