Current equation of state (EOS) models for xenon show substantial differences in the Hugoniot above 100 GPa, prompting the need for an improved understanding of xenon's behavior at extreme conditions. We performed shock compression experiments on liquid xenon to determine the Hugoniot up to 840 GPa, using these results to validate density functional theory (DFT) simulations. Despite the nearly fivefold compression, we find that the limiting Thomas-Fermi theory, exact in the high density limit, does not accurately describe the system. Combining the experimental data and DFT calculations, we developed a free-energy-based, multiphase EOS capable of describing xenon over a wide range of pressures and temperatures.