The magnetic hyperfine field and electric-field gradient at isolated lanthanide impurities in an Fe host lattice are calculated from first principles, allowing for the first time a qualitative and quantitative understanding of an experimental data set collected over the past 40 years. It is demonstrated that the common Local Density Approximation leads to quantitatively and qualitatively wrong results, while the LDA+U method performs much better. In order to avoid pitfalls inherent to the LDA+U method, a careful strategy had to be used, which will be described in detail. The lanthanide 4f spin moment is found to couple antiferromagnetically to the magnetization of the Fe lattice, in agreement with the model of Campbell and Brooks. There is strong evidence for a delocalization/localization transition that is shifted from Ce to at least Pr and maybe further up to Sm. This shift is interpreted in terms of the effective pressure felt by lanthanides in Fe. Implications for resolving ambiguities in the determination of delocalization in pure lanthanide metals under pressure are discussed. For the localized lanthanides, Yb is shown to be divalent in this host lattice, while all others are trivalent (including Eu, the case of Tm is undecided). The completely filled and well-bound 5p shell of the lanthanides is shown to have a major and unexpected influence on the dipolar hyperfine field and on the electric-field gradient, a feature that can be explained by their 1/r^3 dependence. An extrapolation to actinides suggests that the same is true for the actinide 6p shell. The case of free lanthanide atoms is discussed as well.