Ab initio studies of the bonding of CO and NO to a NiO(100) surface are presented. As has been shown by Pacchioni et al. (Pacchioni, G.; Di Valentin, C.; Dominguez-Ariza, D.; Illas, F.; Bredow, T.; Kluner, T.; Staemmler, V. J. Phys.: Condens. Matter 2004, 16, S2497), density functional theory (DFT) fails in predicting accurately the bonding of CO and NO to a NiO(100) surface. In particular, in the case of the NO-NiO(100) system, DFT gives a physically incorrect picture of the bonding. Although the second-order complete active space perturbation theory (CASPT2) method gives qualitatively correct results, still, some uncertainty exists regarding the experimentally predicted value of the adsorption energy. We show that an accurate description of the bonding in the CO-NiO(100) and NO-NiO(100) systems, in fact, represents a challenge to theory, and we will identify the origin of the underestimated bond strength by using different ab initio approaches, and cluster models of systematically increasing size.