The Group 18 elements (noble gases) were the last ones in the periodic system to have not been encountered in perovskite structures. We herein report the synthesis of a new group of double perovskites KM(XeNaO6 ) (M=Ca, Sr, Ba) containing framework-forming xenon. The structures of the new compounds, like other double perovskites, are built up of the alternating sequence of corner-sharing (XeO6 ) and (NaO6 ) octahedra arranged in a three-dimensional rocksalt order. The fact that xenon can be incorporated into the perovskite structure provides new insights into the problem of Xe depletion in the atmosphere. Since octahedrally coordinated Xe(VIII) and Si(IV) exhibit close values of ionic radii (0.48 and 0.40 Å, respectively), one could assume that Xe(VIII) can be incorporated into hyperbaric frameworks such as MgSiO3 perovskite. The ability of Xe to form stable inorganic frameworks can further extend the rich and still enigmatic chemistry of this noble gas.