Xenon, which is quite inert under ambient conditions, may become reactive under pressure. The possibility of the formation of stable xenon oxides and silicates in the interior of the Earth could explain the atmospheric missing xenon paradox. Using an ab initio evolutionary algorithm, we predict the existence of thermodynamically stable Xe-O compounds at high pressures (XeO, XeO(2) and XeO(3) become stable at pressures above 83, 102 and 114 GPa, respectively). Our calculations indicate large charge transfer in these oxides, suggesting that large electronegativity difference and high pressure are the key factors favouring the formation of xenon compounds. However, xenon compounds cannot exist in the Earth's mantle: xenon oxides are unstable in equilibrium with the metallic iron occurring in the lower mantle, and xenon silicates are predicted to decompose spontaneously at all mantle pressures (<136 GPa). However, it is possible that xenon atoms may be retained at defects in mantle silicates and oxides.