Proline dipeptidase (prolidase) was purified from cell extracts of the proteolytic, hyperthermophilic archaeon Pyrococcus furiosus by multistep chromatography. The enzyme is a homodimer (39.4 kDa per subunit) and as purified contains one cobalt atom per subunit. Its catalytic activity also required the addition of Co2+ ions (Kd, 0.24 mM), indicating that the enzyme has a second metal ion binding site. Co2+ could be replaced by Mn2+ (resulting in a 25% decrease in activity) but not by Mg2+, Ca2+, Fe2+, Zn2+, Cu2+, or Ni2+. The prolidase exhibited a narrow substrate specificity and hydrolyzed only dipeptides with proline at the C terminus and a nonpolar amino acid (Met, Leu, Val, Phe, or Ala) at the N terminus. Optimal prolidase activity with Met-Pro as the substrate occurred at a pH of 7.0 and a temperature of 100°C. The N-terminal amino acid sequence of the purified prolidase was used to identify in the P. furiosus genome database a putative prolidase-encoding gene with a product corresponding to 349 amino acids. This gene was expressed in Escherichia coli and the recombinant protein was purified. Its properties, including molecular mass, metal ion dependence, pH and temperature optima, substrate specificity, and thermostability, were indistinguishable from those of the native prolidase from P. furiosus. Furthermore, the Km values for the substrate Met-Pro were comparable for the native and recombinant forms, although the recombinant enzyme exhibited a twofold greater Vmax value than the native protein. The amino acid sequence of P. furiosus prolidase has significant similarity with those of prolidases from mesophilic organisms, but the enzyme differs from them in its substrate specificity, thermostability, metal dependency, and response to inhibitors. The P. furiosus enzyme appears to be the second Co-containing member (after methionine aminopeptidase) of the binuclear N-terminal exopeptidase family.