A growing body of theoretical and experimental evidence suggests that inert gases (He, Ne, Ar, Kr, Xe, Rn) become less and less inert under increasing pressure. Here we use crystal structure prediction software based on the ab initio evolutionary algorithm, named uspex, to predict stable compounds of Xe and Na at pressures below 100 GPa, and we find three stable compounds, NaXe, ${\mathrm{NaXe}}_{3}$, and ${\mathrm{NaXe}}_{4}$. The NaXe belongs to a well-known cubic CsCl structure type. ${\mathrm{NaXe}}_{4}$'s structure is common in amphiboles, whereas ${\mathrm{NaXe}}_{3}$ has a unique structure, analogous to the ``post-perovskite'' orthorhombic ${\mathrm{CaIrO}}_{3}$-type structure with Ir atoms removed. NaXe, ${\mathrm{NaXe}}_{3}$, and ${\mathrm{NaXe}}_{4}$ are found to be metallic.