Atomistic scale calculations reveal that cobalt islands on Cu(001), as they grow in size, undergo unusual shape evolution. The strain relief in the Co islands is predicted to have a strong effect on the shape of the islands and the morphology of the substrate in the early stage of the film growth. We show that strain and stress at the interface vary strongly on an atomic scale. Our results demonstrate that the strain relief in the early stage of heteroepitaxy is more complicated that suggested by simple considerations based on the lattice mismatch of bulk materials.