The performance of supported metal catalysts, such as nickel nanoparticles decorating yttria-stabilized zirconia (YSZ), depends on their microstructure and the metal-support interface. Here, we have used spin polarized density functional theory (DFT) to evaluate different Ni cluster geometries and determined the electronic structure of the most stable configurations. We have described the interaction of Nin (n = 1-10) clusters supported on the cubic ZrO2(111) and YSZ(111) surfaces, which show a preference for pyramidal shapes rather than flat structures wetting the surface. The interfacial interaction is characterized by charge transfer from the cluster to the surface. We also show how yttrium, present in YSZ, affects the Ni-Ni interaction. Through analysing the difference between the cohesive energy and the clustering energy, we show the preference of Ni-Ni bond formation over Ni-surface interaction; this energy difference decreases with the increase of the Nin cluster size. From the evaluation of the Ni atomic hopping rates on YSZ, we have demonstrated that under different temperature conditions, Ni atoms aggregate with other atoms and clusters, which affects the cluster size stability.