We present a newly developed scheme for atomic relaxations of magnetic supported clusters. Our approach is based on the full potential Korringa-Kohn-Rostoker Green\'s function method and the second moment tight-binding approximation for many-body potentials. We demonstrate that only a few iterations in ab initio calculations are necesssary to find an equilibrium structure for supported clusters. As an example, we present our results for small Co clusters on Cu(001). Changes in the electronic and magnetic states of the clusters due to atomic relaxations are revealed.