This paper presents an exploratory study of the binding interactions of xenon with the surface of several different proteins in the solution and solid states using both conventional and hyperpolarized Xe-129 NMR. The generation of hyperpolarized Xe-129 by spin exchange optical pumping affords an enhancement by 3-4 orders of magnitude of its NMR signal. As a result, it is possible to observe Xe directly bound to the surface of micromolar quantities of lyophilized protein. The highly sensitive nature of die Xe-129 line shape and chemical shift are used as indicators for the conditions most likely to yield maximal dipolar contact between Xe-129 nuclei and nuclear spins situated on the protein. This is an intermediate step toward achieving the ultimate goal of NMR enhancement of the binding-site nuclei by polarization transfer from hyperpolarized Xe-129. The hyperpolarized Xe-129 spectra resulting from exposure of four different proteins in the lyophilized, powdered Form have been examined for evidence of binding. Each of the proteins, namely, metmyoglobin, methemoglobin, hen egg white lysozyme, and soybean lipoxygenase, yielded a distinctly different NMR line shape. With the exception of lysozyme, the proteins all possess a paramagnetic iron center which can be expected to rapidly relax the Xe-129 and produce a net shift in its resonance position if the noble gas atom occupies specific binding sites near the iron. At temperatures from 223 to 183 K, NMR signals were observed in the 0-40 ppm chemical shift range, relative to Xe in the gas phase. The signals broadened and shifted downfield as the temperature was reduced, indicating that Xe is exchanging between the gas phase and internal or external binding sites of the proteins. Additionally, conventional Xe-129 NMR studies of metmyoglobin and lipoxygenase in the solution state are presented. The temperature dependence of the chemical shift and line shape indicate exchange of Xe between adsorption sites on lipoxygenase and Xe in the solvent on the slow to intermediate exchange time scale. The NMR results are compared with N-2, Xe, and CH4 gas adsorption isotherms, It is found that lipoxygenase is unique among the proteins studied in possessing a relatively high affinity for gas molecules, and in addition, demonstrating the most clearly resolved adsorbed Xe-129 NMR peak in the lyophilized state.