We have determined the effective exchange interactions in the random magnetic overlayers on a nonmagnetic substrate by a mapping of the accurate ab initio total energies onto a classical two-dimensional Heisenberg Hamiltonian. The electronic structure is determined within the tight-binding linear muffin-tin orbital method combined with the surface Green function technique while the effect of a disorder is included using the coherent potential approximation.We employ both the magnetic-force and the vertex-cancellation theorems to evaluate the concentration dependence on the overlayer exchange interactions. The formalism is applied to the magnetic overlayers on the fcc-Cu(001) substrate.