Protein interiors contain void space that can bind small gas molecules. Determination of gas pathways and kinetics in proteins has been an intriguing and challenging task. Here, we combined computational methods and the hyperpolarized xenon-129 chemical exchange saturation transfer (hyper-CEST) NMR technique to investigate xenon (Xe) exchange kinetics in maltose-binding protein (MBP). A salt bridge ∼9 Å from the Xe-binding site formed upon maltose binding and slowed the Xe exchange rate, leading to a hyper-CEST 129Xe signal from maltose-bound MBP. Xe dissociation occurred faster than dissociation of the salt bridge, as shown by 13C NMR spectroscopy and variable-B1 hyper-CEST experiments. "Xe flooding" molecular dynamics simulations identified a surface hydrophobic site, V23, that has good Xe binding affinity. Mutations at this site confirmed its role as a secondary exchange pathway in modulating Xe diffusion. This shows the possibility for site-specifically controlling xenon protein-solvent exchange. Analysis of the available MBP structures suggests a biological role of MBP's large hydrophobic cavity to accommodate structural changes associated with ligand binding and protein-protein interactions.