The structure of Escherichia blattae non-specific acid phosphatase (EB-NSAP) has been determined at 1.9 A resolution with a bound sulfate marking the phosphate-binding site. The enzyme is a 150 kDa homohexamer. EB-NSAP shares a conserved sequence motif not only with several lipid phosphatases and the mammalian glucose-6-phosphatases, but also with the vanadium-containing chloroperoxidase (CPO) of Curvularia inaequalis. Comparison of the crystal structures of EB-NSAP and CPO reveals striking similarity in the active site structures. In addition, the topology of the EB-NSAP core shows considerable similarity to the fold of the active site containing part of the monomeric 67 kDa CPO, despite the lack of further sequence identity. These two enzymes are apparently related by divergent evolution. We have also determined the crystal structure of EB-NSAP complexed with the transition-state analog molybdate. Structural comparison of the native enzyme and the enzyme-molybdate complex reveals that the side-chain of His150, a putative catalytic residue, moves toward the molybdate so that it forms a hydrogen bond with the metal oxyanion when the molybdenum forms a covalent bond with NE2 of His189.