The intermolecular interactions of noble gases in biological systems are associated with numerous biochemical responses, including apoptosis, inflammation, anesthesia, analgesia, and neuroprotection. The molecular modes of action underlying these responses are largely unknown. This is in large part due to the limited experimental techniques to study protein-gas interactions. The few techniques that are amenable to such studies are relatively low-throughput and require large amounts of purified proteins. Thus, they do not enable the large-scale analyses that are useful for protein target discovery. Here, we report the application of stability of proteins from rates of oxidation (SPROX) and limited proteolysis (LiP) methodologies to detect protein-xenon interactions on the proteomic scale using protein folding stability measurements. Over 5000 methionine-containing peptides and over 5000 semi-tryptic peptides, mapping to ∼1500 and ∼950 proteins, respectively, in the yeast proteome, were assayed for Xe-interacting activity using the SPROX and LiP techniques. The SPROX and LiP analyses identified 31 and 60 Xe-interacting proteins, respectively, none of which were previously known to bind Xe. A bioinformatics analysis of the proteomic results revealed that these Xe-interacting proteins were enriched in those involved in ATP-driven processes. A fraction of the protein targets that were identified are tied to previously established modes of action related to xenon's anesthetic and organoprotective properties. These results enrich our knowledge and understanding of biologically relevant xenon interactions. The sample preparation protocols and analytical methodologies developed here for xenon are also generally applicable to the discovery of a wide range of other protein-gas interactions in complex biological mixtures, such as cell lysates.