Atomic scale simulations show that Co clusters embedded in Cu surfaces are always more stable than the adsorbed clusters often observed experimentally. Spin-polarized electronic structure calculations based on a self-consistent tight-binding method reveal that, unlike gas-phase clusters, ferromagnetic Co clusters embedded in Cu do not exhibit "magnetic magic numbers". This is explained in terms of the coordination geometry imposed on the clusters by the substrate.