Staphylococcus simulans lysostaphin cleaves pentaglycine cross-bridges between stem peptides in the peptidoglycan of susceptible staphylococci, including S. aureus. This enzyme consists of an N-terminal catalytic domain and a cell wall binding domain (SH3b), which anchors the protein to peptidoglycan. Although structures of SH3bs from lysostaphin are available, the binding modes of peptidoglycan to these domains are still unclear. We have solved the crystal structure of the lysostaphin SH3b domain in complex with a pentaglycine peptide representing the peptidoglycan cross-bridge. The structure identifies a groove between β1 and β2 strands as the pentaglycine binding site. The structure suggests that pentaglycine specificity of the SH3b arises partially directly by steric exclusion of Cβ atoms in the ligand and partially indirectly due to the selection of main chain conformations that are easily accessible for glycine, but not other amino acid residues. We have revealed further interactions of SH3b with the stem peptides with the support of bioinformatics tools. Based on the structural data we have attempted engineering of the domain specificity and have investigated the relevance of the introduced substitutions on the domain binding and specificity, also in the contexts of the mature lysostaphin and of its bacteriolytic activity.