The magnetic hyperfine field and electric-field gradient at isolated lanthanide impurities in an Fe host lattice are calculated from first principles, allowing 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 combination of free ion calculations and "constrained density matrix" calculations is proposed and tested. Quantitative results for the exchange field and crystal field parameters are obtained (B-exc=+420 T, B-0(4)=-1000 cm(-1), B-0(6)=-800 cm(-1)), showing in particular how crystal field effects influence the hyperfine fields for the lightest and heaviest lanthanides. The hyperfine fields are shown to be dominated by the 4f orbital contribution, with small corrections due to the spin dipolar and Fermi contact fields. The latter is found to be constant for all lanthanides, a feature that is understood by a modified version of the well-known core polarization mechanism for 3d hyperfine fields. Spin dipolar fields and electric-field gradients have apart from a 4f contribution a surprisingly strong contribution due to the completely filled lanthanide 5p orbitals-the mechanism behind this is explained. The lanthanide 4f spin moment is found to couple antiparallel 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 temperature dependence of the hyperfine fields is discussed as well.