Exopolysaccharides are required for the development and integrity of biofilms produced by a wide variety of bacteria. In staphylococci, partial de-N-acetylation of the exopolysaccharide poly-β-1,6-N-acetyl-d-glucosamine (PNAG) by the extracellular protein IcaB is required for biofilm formation. To understand the molecular basis for PNAG de-N-acetylation, the structure of IcaB from Ammonifex degensii (IcaBAd) has been determined to 1.7 Å resolution. The structure of IcaBAd reveals a (β/α)7 barrel common to the family four carbohydrate esterases (CE4s) with the canonical motifs circularly permuted. The metal dependence of IcaBAd is similar to most CE4s showing the maximum rates of de-N-acetylation with Ni2+, Co2+, and Zn2+. From docking studies with β-1,6-GlcNAc oligomers and structural comparison to PgaB from Escherichia coli, the Gram-negative homologue of IcaB, we identify Arg-45, Tyr-67, and Trp-180 as key residues for PNAG binding during catalysis. The absence of these residues in PgaB provides a rationale for the requirement of a C-terminal domain for efficient deacetylation of PNAG in Gram-negative species. Mutational analysis of conserved active site residues suggests that IcaB uses an altered catalytic mechanism in comparison to other characterized CE4 members. Furthermore, we identified a conserved surface-exposed hydrophobic loop found only in Gram-positive homologues of IcaB. Our data suggest that this loop is required for membrane association and likely anchors IcaB to the membrane during polysaccharide biosynthesis. The work presented herein will help guide the design of IcaB inhibitors to combat biofilm formation by staphylococci.IcaB is a poly-β-1,6-N-acetyl-d-glucosamine (PNAG) deacetylase required for polysaccharide intercellular adhesion-dependent biofilm formation by staphylococci. The structure of Ammonifex degensii IcaB has been determined and its catalytic mechanism and localization characterized. IcaB is a membrane-associated PNAG deacetylase that uses an altered catalytic mechanism relative to other family 4 carbohydrate esterases. First structural characterization of a Gram-positive PNAG deacetylase.