We describe the first measurement of the near IR spectrum of the NO-Kr van der Waals complex. A variant of IR-REMPI double-resonance spectroscopy is employed in which the IR and UV lasers are scanned simultaneously in such a way that throughout the scan the sum of the two photon energies is kept constant, matching a UV resonance of the system. In the region of the first overtone vibration of the NO monomer, we observe several rotationally resolved bands for the NO-Kr complex. In addition to the origin band located at 3723.046 cm(-1), we observe excited as well as hot bands involving the excitation of one or two quanta of z-axis rotation. Another band is assigned to the excitation of one quantum of bending vibration. The experimental spectra are compared with results of bound-state calculations for a new set of potential energy surfaces calculated at the spin-restricted coupled cluster level. For the average vibration-rotation energies, there is excellent agreement between the theoretical results based on the coupled states (CS) approximation and the full close-coupling (CC) treatment. Finer details like the electrostatic splitting and the P-type doubling of the rotational levels are accounted for only within the CC formalism. The comparison of the CC results with the measured spectra confirms the high quality of the PESs, However, the high resolution of the experiments is sufficient. to identify some inaccuracies in the difference between the potential energy surfaces of A' and A '' reflection symmetry.