Bacterial cell wall is a polymer of considerable complexity that is in constant equilibrium between synthesis and recycling. AmpDh3 is a periplasmic zinc protease of Pseudomonas aeruginosa, which is intimately involved in cell-wall remodeling. We document the hydrolytic reactions that this enzyme performs on the cell wall. The process removes the peptide stems from the peptidoglycan, the major constituent of the cell wall. We document that the majority of the reactions of this enzyme takes place on the polymeric insoluble portion of the cell wall, as opposed to the fraction that is released from it. We show that AmpDh3 is tetrameric both in crystals and in solution. Based on the X-ray structures of the enzyme in complex with two synthetic cell-wall-based ligands, we present for the first time a model for a multivalent anchoring of AmpDh3 onto the cell wall, which lends itself to its processive remodeling.