Protein glycosylation with O-linked N-acetylglucosamine (O-GlcNAc) is a post-translational modification of serine/ threonine residues in nucleocytoplasmic proteins. O-GlcNAc has been shown to play a role in many different cellular processes and O-GlcNAcylation is often found at sites that are also known to be phosphorylated. Unlike phosphorylation, O-GlcNAc levels are regulated by only two enzymes, O-GlcNAc transferase (OGT) and O-GlcNAc hydrolase (O-GlcNAcase or OGA). So far, no obvious consensus sequence has been found for sites of O-GlcNAcylation. Additionally, O-GlcNAcase recognizes and cleaves all O-GlcNAcylated proteins, independent of their sequence. In this work, we generate and analyze five models of O-GlcNAcylated peptides in complex with a bacterial OGA. Each of the five glycopeptides bind to OGA in a similar fashion, with OGA–peptide interactions primarily, but not exclusively, involving the peptide backbone atoms, thus explaining the lack of sensitivity to peptide sequence. Nonetheless, differences in peptide sequences, particularly at the −1 to −4 positions, lead to variations in predicted affinity, consistent with observed experimental variations in enzyme kinetics. The potential exists, therefore, to employ the present analysis to guide the development glycopeptide-specific inhibitors, or conversely, the conversion of OGA into a reagent that could target specific O-GlcNAcylated peptide sequences.