Structural relaxations in small Co islands on the Cu(001) surface are investigated performing atomistic calculations. We demonstrate that the strain relief at the metal interface in the early stages of heteroepitaxy is more complicated than suggested by simple considerations based on the small mismatch between the Co and Cu bulk metals. We found that the strain distribution in the surface region near the islands varies strongly on an atomic scale. The effect of strain on the shape of the Co islands is revealed. Diffusion on the top of strained islands and edge diffusion are considered.