HisB from Escherichia coli is a bifunctional enzyme catalyzing the sixth and eighth steps of l-histidine biosynthesis. The N-terminal domain (HisB-N) possesses histidinol phosphate phosphatase activity, and its crystal structure shows a single domain with fold similarity to the haloacid dehalogenase (HAD) enzyme family. HisB-N forms dimers in the crystal and in solution. The structure shows the presence of a structural Zn2+ ion stabilizing the conformation of an extended loop. Two metal binding sites were also identified in the active site. Their presence was further confirmed by isothermal titration calorimetry. HisB-N is active in the presence of Mg2+, Mn2+, Co2+, or Zn2+, but Ca2+ has an inhibitory effect. We have determined structures of several intermediate states corresponding to snapshots along the reaction pathway, including that of the phosphoaspartate intermediate. A catalytic mechanism, different from that described for other HAD enzymes, is proposed requiring the presence of the second metal ion not found in the active sites of previously characterized HAD enzymes, to complete the second half-reaction. The proposed mechanism is reminiscent of two-Mg2+ ion catalysis utilized by DNA and RNA polymerases and many nucleases. The structure also provides an explanation for the inhibitory effect of Ca2+.