Fast gas-phase hydrogen/deuterium exchange mediated by ND₃ gas and measured by mass spectrometry (gas-phase HDX-MS) is a largely unharnessed, fast, and sensitive method for probing primary- and higher-order polypeptide structure. Labeling of heteroatom-bound non-amide hydrogens in a sub-millisecond time span after electrospray ionization by ND₃ gas can provide structural insights into protein conformers present in solution. Here, we have explored the use of gas-phase HDX-MS for probing the higher-order structure and binding interfaces of protein complexes originating from native solution conditions. Lysozyme ions bound by an oligosaccharide incorporated less deuterium than the unbound ion. Similarly, trypsin ions showed reduced deuterium uptake when bound by the peptide ligand vasopressin. Our results are in good agreement with crystal structures of the native protein complexes, and illustrate that gas-phase HDX-MS can provide a sensitive and simple approach to measure the number of heteroatom-bound non-amide side-chain hydrogens involved in the binding interface of biologically relevant protein complexes.