During Staphylococcus aureus infections, the immune response generates reactive oxygen species that cause DNA damage including modification of nucleotide bases. After removal of the defective base, the S. aureus base excision repair process requires an endonuclease IV (Nfo) which hydrolyzes the phosphodiester bond 5′ to the abasic nucleotide. This class of enzymes, typified by the enzyme from Gram-negative E. coli, contains a catalytic site with three metal ions, usually all Zn2+, or Zn2+ and Mg2+. The high-resolution crystal structure of the Nfo from the Gram-positive organism S. aureus complexed to sulfate reveals two Fe2+ and one Zn2+ ions whose identity were confirmed by wavelength-dependent anomalous difference Fourier maps and were also present in the structure of an Nfo from the Gram-positive Geobacillus kaustophilus. These two structures, and a third Nfo from Gram-positive Bacillus anthracis, have a previously undescribed water molecule liganded to one Fe forming octahedral coordination geometry. The water molecule is also hydrogen-bonded to Tyr33, an active site residue that is conserved in many similar Gram-positive bacteria, but which is Phe in all Gram-negative species. Interestingly, a Tyr33→Phe mutant structure lacks this water, which is likely displaced by a conformational change of Tyr71. Unexpectedly, the mutant enzyme is catalytically faster than the wild-type S. aureus Nfo.