The influence on the growth of cobalt (Co)-based nanostructures of a surface carbide (Ni2C) layer formed at the Ni(100) surface is revealed via complementary scanning tunneling microscopy (STM) measurements and first-principles calculations. On clean Ni(100) below 200 °C in the sub-monolayer regime, Co forms randomly distributed two-dimensional (2D) islands, while on Ni2C it grows in the direction perpendicular to the surface as well, thus forming two-atomic-layers high islands. We present a simple yet powerful model that explains the different Co growth modes for the two surfaces. A jagged step decoration, not visible on stepped Ni(100), is present on Ni2C. This contrasting behavior on Ni2C is explained by the sharp differences in the mobility of Co atoms for the two cases. By increasing the temperature, Co dissolution is activated with almost no remaining Co at 250 °C on Ni(100) and Co islands still visible on the Ni2C surface up to 300 °C. The higher thermal stability of Co above the Ni2C surface is rationalized by ab initio calculations, which also suggest the existence of a vacancy-assisted mechanism for Co dissolution in Ni(100). The methodology presented in this paper, combining systematically STM measurements with first-principles calculations and computational modelling, opens the way to controlled engineering of bimetallic surfaces with tailored properties.