Colicin M (ColM) is the only enzymatic colicin reported to date that inhibits cell wall peptidoglycan biosynthesis. It catalyzes the specific degradation of the lipid intermediates involved in this pathway, thereby provoking lysis of susceptible Escherichia coli cells. A gene encoding a homologue of ColM was detected within the exoU-containing genomic island A carried by certain pathogenic Pseudomonas aeruginosa strains. This bacteriocin (pyocin) that we have named PaeM was crystallized, and its structure with and without an Mg(2+) ion bound was solved. In parallel, site-directed mutagenesis of conserved PaeM residues from the C-terminal domain was performed, confirming their essentiality for the protein activity both in vitro (lipid II-degrading activity) and in vivo (cytotoxicity against a susceptible P. aeruginosa strain). Although PaeM is structurally similar to ColM, the conformation of their active sites differs radically; in PaeM, residues essential for enzymatic activity and cytotoxicity converge toward a same pocket, whereas in ColM they are spread along a particularly elongated active site. We have also isolated a minimal domain corresponding to the C-terminal half of the PaeM protein and exhibiting a 70-fold higher enzymatic activity as compared with the full-length protein. This isolated domain of the PaeM bacteriocin was further shown to kill E. coli cells when addressed to the periplasm of these bacteria.