The adsorption of carbon monoxide on the NiO(100) surface has been investigated theoretically with firstprinciples Hartree-Fock, density functional, and hybrid methods. The surface was modeled with embedded clusters and periodic slabs that were shown to give similar results for the CO adsorption energy, adsorbate geometry, and vibration frequency. The effect of the description of the electron exchange and correlation given by the various methods on the interaction of CO and NiO has been investigated. While the inclusion of electron correlation leads to an increase of the calculated interaction energy compared to the Hartree-Fock approach and improves the agreement with experiment considerably, the role of electron exchange is less clear. Close agreement of calculated and experimental NiO/CO adsorption energies was achieved by using a density functional approach for exchange and correlation, but at the same time a large deviation of the calculated C-O frequency shift from the experimental value was obtained. This is explained by the role of exchange in the description of the substrate electronic structure. Best overall agreement for energetic and spectroscopic features was achieved by a hybrid approach that combines exact Hartree-Fock exchange with a correlation functional.