We present a new technique which allows the fully {em ab initio} calculation of the chemical potential of a substitutional impurity in a high-temperature crystal, including harmonic and anharmonic lattice vibrations. The technique uses the combination of thermodynamic integration and reference models developed recently for the {em ab initio} calculation of the free energy of liquids and anharmonic solids. We apply the technique to the case of the substitutional oxygen impurity in h.c.p. iron under Earths core conditions, which earlier static {em ab initio} calculations indicated to be thermodynamically very unstable. Our results show that entropic effects arising from the large vibrational amplitude of the oxygen impurity give a major reduction of the oxygen chemical potential, so that oxygen dissolved in h.c.p. iron may be stabilised at concentrations up a few mol % under core conditions.