The clean and cobalt-covered NiO(001) surface was studied by surface x-ray diffraction. The NiO(001) surface prepared by annealing in air at 1000 ^°C is characterized by a strong expansion of the top interlayer spacing ([approximate]14 % relative to the bulk NiO-spacing of 2.085 Å) and an outward relaxation (0.28 Å) of the oxygen atoms, which can be related to a high (27 %) concentration of oxygen vacancy defects. In addition we find an oxygen-layer (most likely as part of the OH– anion) on top of the surface Ni atoms at a distance of 2.33 Å. Deposition of 0.8 monolayers of Co induces a complex surface restructuring involving the formation of double layer CoO-islands above an oxygen deficient interfacial oxide layer ([NiCo]O0.5) in registry with the underlying NiO single crystal. Our results support previous spectroscopic studies suggesting the presence of uncompensated interfacial spins responsible for the exchange bias.