We present an ab initio description of the spin Hall effect in metals. Our approach is based on density functional theory in the framework of a fully relativistic Korringa-Kohn-Rostoker method and the solution of a linearized Boltzmann equation including the scattering-in term (vertex corrections). The skew scattering mechanism at substitutional impurities is considered. Spin-orbit coupling in the host as well as at the impurity atom and the influence of spin-flip processes are fully taken into account. A sign change of the spin Hall effect in Cu and Au hosts is obtained as a function of the impurity atom, and even light elements like Li can cause a strong effect. It is shown that the gigantic spin Hall effect in Au can be caused by skew scattering at C and N impurities which are typical contaminations in a vacuum chamber.