The velocity distributions of the laser-induced desorption of NO molecules from an epitaxially grown film of NiO(100) on Ni(100) have been studied [Mull et al., J. Chem. Phys., 1992, 96, 7108]. A pronounced bimodality of velocity distributions has been found, where the NO molecules desorbing with higher velocities exhibit a coupling to the rotational quantum states J. In this article we present simulations of state resolved velocity distributions on a full ab initio level. As a basis for this quantum mechanical treatment a 4D potential energy surface (PES) was constructed for the electronic ground and a representative excited state, using a NiO5Mg(18+)13 cluster. The PESs of the electronic ground and an excited state were calculated at the CASPT2 and the configuration interaction (CI) level of theory, respectively. Multi-dimensional quantum wave packet simulations on these two surfaces were performed for different sets of degrees of freedom. Our key finding is that at least a 3D wave packet simulation, in which the desorption coordinate Z, polar angle theta and lateral coordinate X are included, is necessary to allow the simulation of experimental velocity distributions. Analysis of the wave packet dynamics demonstrates that essentially the lateral coordinate, which was neglected in previous studies [Klüner et al., Phys. Rev. Lett. 1998, 80, 5208], is responsible for the experimentally observed bimodality. An extensive analysis shows that the bimodality is due to a bifurcation of the wave packet on the excited state PES, where the motion of the molecule parallel to the surface plays a decisive role.