Studies of the Earth's atmosphere have shown that more than 90% of the expected amount of Xe is depleted, a finding often referred to as the 'missing Xe paradox'. Although several models for a Xe reservoir have been proposed, whether the missing Xe could be contained in the Earth's inner core has not yet been answered. The key to addressing this issue lies in the reactivity of Xe with Fe/Ni, the main constituents of the Earth's core. Here, we predict, through first-principles calculations and unbiased structure searching techniques, a chemical reaction of Xe with Fe/Ni at the temperatures and pressures found in the Earth's core. We find that, under these conditions, Xe and Fe/Ni can form intermetallic compounds, of which XeFe3 and XeNi3 are energetically the most stable. This shows that the Earth's inner core is a natural reservoir for Xe storage and provides a solution to the missing Xe paradox.