We report results from high pressure and temperature experiments that provide evidence for the reactivity of xenon with water ice at pressures above 50 GPa and a temperature of 1500 K--conditions that are found in the interiors of Uranus and Neptune. The x-ray data are sufficient to determine a hexagonal lattice with four Xe atoms per unit cell and several possible distributions of O atoms. The measurements are supplemented with ab initio calculations, on the basis of which a crystallographic structure with a Xe4O12H12 primitive cell is proposed. The newly discovered compound is formed in the stability fields of superionic ice and η-O2, and has the same oxygen subnetwork as the latter. Furthermore, it has a weakly metallic character and likely undergoes sublattice melting of the H subsystem. Our findings indicate that Xe is expected to be depleted in the atmospheres of the giant planets as a result of sequestration at depth.