Bacterial peptide deformylase (PDF) belongs to a sub-family of metalloproteases that catalyse the removal of the N-terminal formyl group from newly synthesised proteins. PDF is essential in prokaryotes and conserved throughout the eubacteria. It is therefore considered an attractive target for developing new antibacterial agents. Here, we report the crystal structures of four bacterial deformylases, free or bound to the naturally occurring antibiotic actinonin, including two from the major bacterial pathogens Pseudomonas aeruginosa and Staphylococcus aureus. The overall tertiary structure is essentially conserved but shows significant differences, namely at the C terminus, which are directly related to the deformylase type (i.e. I or II) they belong to. The geometry around the catalytic metal ion exhibits a high level of similarity within the different enzymes, as does the binding mode of actinonin to the various deformylases. However, some significant structural differences are found in the vicinity of the active site, highlighting the structural and molecular requirements for the design of a deformylase inhibitor active against a broad spectrum of bacterial strains.