Characterizing structures of protein complexes and their disease-related aberrations is essential to understanding molecular mechanisms of many biological processes. Electrospray ionization coupled with hybrid ion mobility/mass spectrometry (ESI-IM/MS) methods offer sufficient sensitivity, sample throughput, and dynamic range to enable systematic structural characterization of proteomes. However, because ESI-IM/MS characterizes ionized protein systems in the gas phase, it generally remains unclear to what extent the protein ions characterized by IM/MS have retained their solution structures. Here, we discuss the first application of our computational structure relaxation approximation [Bleiholder, C.; et al. J. Phys. Chem. B 2019, 123 (13), 2756-2769] to assign structures of protein complexes in the range from ∼16 to ∼60 kDa from their "native" IM/MS spectra. Our analysis shows that the computed IM/MS spectra agree with the experimental spectra within the errors of the methods. The structure relaxation approximation (SRA) indicates that native backbone contacts appear largely retained in the absence of solvent for the investigated protein complexes and charge states. Native contacts between polypeptide chains of the protein complex appear to be retained to a comparable extent as contacts within a folded polypeptide chain. Our computations also indicate that the hallmark "compaction" often observed for protein systems in native IM/MS measurements appears to be a poor indicator of the extent to which native residue-residue interactions are lost in the absence of solvent. Further, the SRA indicates that structural reorganization of the protein systems in IM/MS measurements appears driven largely by remodeling of the protein surface that increases its hydrophobic content by approximately 10%. For the systems studied here, this remodeling of the protein surface appears to occur mainly by structural reorganization of surface-associated hydrophilic amino acid residues not associated with β-strand secondary structure elements. Properties related to the internal protein structure, as assessed by void volume or packing density, appear unaffected by remodeling of the surface. Taken together, the structural reorganization of the protein surface appears to be generic in nature and to sufficiently stabilize protein structures to render them metastable on the time scale of IM/MS measurements.