We study substitutional fluorine, chlorine and bromine impurities at CeO2(111), and their effects on the oxygen chemistry of the surface, using density functional theory. We find that impurity formation results in a halide ion and one Ce3+ ion for all three halogens, although the formation energy depends strongly on the identity of the halogen; however, once formed, all three halogens exhibit a similar propensity to form impurity-impurity pairs. Furthermore, while the effects of halogen impurities on oxygen vacancy formation are marginal, they are more significant for oxygen molecule adsorption, due to electron transfer from the Ce3+ ion which results in an adsorbed superoxide molecule. We also consider the displacement of a halide ion on to the surface by half of an oxygen molecule, and find that the energy required to do so depends strongly not only on the identity of the halogen, but also on whether or not a second halogen impurity, with its associated Ce3+ ion, is present; if it is, then the process is greatly facilitated. Overall, our results demonstrate the existence of a rich variety of ways in which the oxygen chemistry of CeO2(111) may be modified by the presence of halogen dopants.