Post-translational modifications usually occur under enzymatic control as a mechanism for regulation of protein activity or localization, but can also occur spontaneously during protein aging and degradation. In contrast, there are few examples of spontaneous post-translational modifications with a significant role in the stability or biochemical function of a bacterial protein. Here we show that the solute-binding protein SAR11_0655 from the abundant marine bacterium ‘Candidatus Pelagibacter ubique’ HTCC1062 contains an unusually stable succinimide residue important for its function in high-affinity binding of the amino acid derivative 5-oxoproline. Spontaneous cyclization of Asn269 to yield a succinimide residue was inferred from electron density in the X-ray crystal structure of SAR11_0655 and confirmed by liquid chromatography-tandem mass spectrometry. Loss of the succinimide modification via the substitution N269A resulted in a >20 °C decrease in thermostability and a 15 to 50-fold decrease in binding affinity for 5-oxoproline. Analysis of sequence conservation indicated that both Asn269 and Asp269 are common among SAR11_0655 homologs, and the N269D variant of SAR11_0655 also showed partial formation of succinimide. Altogether, this work uncovers a novel mechanism that facilitates high-affinity binding in solute-binding proteins and provides a potential basis for identification and design of structurally encoded succinimide residues for engineering of protein thermostability.