We present calculations of solid state NMR magnetic shielding in metals, which includes both the orbital and the complete spin response of the system in a consistent way. The latter contains an induced spin-polarization of the core states and needs an all-electron self-consistent treatment. In particular, for transition metals, the spin hyperfine field originates not only from the polarization of the valence s-electrons, but the induced magnetic moment of the d-electrons polarizes the core s-states in opposite direction. The method is based on DFT and the augmented plane wave approach as implemented in the WIEN2k code. A comparison between calculated and measured NMR shifts indicates that first-principle calculations can obtain converged results and are more reliable than initially concluded based on previous publications. Nevertheless large k-meshes (up to 2 000 000 k-points in the full Brillouin-zone) and some Fermi-broadening are necessary. Our results show that, in general, both spin and orbital components of the NMR shielding must be evaluated in order to reproduce experimental shifts, because the orbital part cancels the shift of the usually highly ionic reference compound only for simple sp-elements but not for transition metals. This development paves the way for routine NMR calculations of metallic systems.