The cold-active protein-tyrosine phosphatase (CAPTPase) of a psychrophile, Shewanella sp., shows high catalytic activity below 20°C. The catalytic residue of CAPTPase is histidine, as opposed to the cysteine of known protein-tyrosine phosphatases (PTPases), and the enzyme protein has three amino acid sequences, Asp-Xaa-His, Gly-Asp-Xaa-Xaa-Asp-Arg and Gly-Asn-His-Glu, that are observed in many protein-serine/threonine phosphatases (PS/TPases). We have determined the crystal structures of CAPTPase at 1.82 Å and the enzyme bound with a phosphate ion at 1.90 Å resolution using X-ray crystallography and the multiple isomorphous replacement method. The final refined models are comprised of 331 amino acid residues, two metal ions, 447 water molecules, and an acetate or phosphate ion in an asymmetric unit. The enzyme protein consists of three β-sheets, termed Sheet I, Sheet I′, and Sheet II, and 14 α-helices. The CAPTPase has a different overall structure from known protein-tyrosine phosphatases. The arrangement of two metal ions, a phosphate ion and the adjacent amino acid residues in the catalytic site of CAPTPase is identical to that of PS/TPases. Thus, it was confirmed that the CAPTPase was a novel PTPase with a conformation similar to the catalytic site of PS/TPase. We speculate that the hydrophobic moiety around the catalytic residue of CAPTPase might play an important role in eliciting high activity at low temperature.