By using an N-body potential scheme constructed by fitting the interaction parameters to accurate first-principles calculations, we investigate the structural stability of Co atoms and clusters deposited on Cu(100). We found that Co atoms and clusters prefer to be embedded inside the substrate, in a way compatible with the formation of a surface alloy observed experimentally. Enhanced stability is achieved when Co atoms are deposited on a preformed Co cluster embedded on the uppermost layer of the substrate. Co atoms deposited on Co islands are best stabilized when they concur to complete the islands, by promoting layer-by-layer growth.