N-Acyl-l-homoserine lactone (AHL) mediated quorum-sensing regulates virulence factor production in a variety of Gram-negative bacteria. Proteins capable of degrading these autoinducers have been called “quorum-quenching” enzymes, can block many quorum-sensing dependent phenotypes, and represent potentially useful reagents for clinical, agricultural, and industrial applications. The most characterized quorum-quenching enzymes to date are the AHL lactonases, which are metalloproteins that belong to the metallo-beta-lactamase superfamily. Here, we report the cloning, heterologous expression, purification, metal content, substrate specificity, and three-dimensional structure of AiiB, an AHL lactonase from Agrobacterium tumefaciens. Much like a homologous AHL lactonase from Bacillus thuringiensis, AiiB appears to be a metal-dependent AHL lactonase with broad specificity. A phosphate dianion is bound to the dinuclear zinc site and the active-site structure suggests specific mechanistic roles for an active site tyrosine and aspartate. To our knowledge, this is the second representative structure of an AHL lactonase and the first of an AHL lactonase from a microorganism that also produces AHL autoinducers. This work should help elucidate the hydrolytic ring-opening mechanism of this family of enzymes and also facilitate the design of more effective quorum-quenching catalysts.