The interplay between structure and magnetic properties of small cobalt clusters embedded in a Cu(001) surface is studied performing ab initio and tight-binding calculations in a fully relaxed geometry. We reveal that, despite the small macroscopic mismatch between Co and Cu, the strain relaxations at the interface have a profound effect on the structure of the clusters and the substrate. The physical mechanism responsible for the strain relaxations in embedded clusters is related to the size-dependent mesoscopic mismatch which has been recently introduced to understand homo- and heteroepitaxial growth at the mesoscale [O. V. Lysenko et al., Phys. Rev. Lett. 89, 126102 (2002)]. We show that the atomic relaxations strongly reduce the magnetic anisotropy energy (MAE) and the orbital magnetic moments of embedded clusters. The largest MAE of about 1.8 meV is found for a single Co atom in the Cu(001) surface. A strong enhancement of the spin magnetic moments in embedded clusters as compared to a single atom of Co incorporated in the Cu(001) surface is found. Magnetic properties of embedded and supported clusters are compared. While in supported clusters the MAE is strongly enhanced at the edge atoms, the immersion of the cluster into the surface and atomic relaxations make the distribution of the local MAE contributions and orbital-moment values almost homogeneous.