Acylpeptide hydrolases (APH; also known as acylam-ino acid releasing enzyme) catalyze the removal of an N-acylated amino acid from blocked peptides. The crystal structure of an APH from the thermophilic arch-aeon Aeropyrum pernix K1 to 2.1 A resolution confirms it to be a member of the prolyl oligopeptidase family of serine proteases. The structure of apAPH is a sym-metric homodimer with each subunit comprised of two domains. The N-terminal domain is a regular seven-bladed β-propeller, while the C-terminal domain has a canonical α/β hydrolase fold and includes the active site and a conserved Ser445-Asp524-His556 catalytic triad. The complex structure of apAPH with an organo- phosphorus substrate, p-nitrophenyl phosphate, has also been determined. The complex structure unam- biguously maps out the substrate binding pocket and provides a basis for substrate recognition by apAPH. A conserved mechanism for protein degradation from archaea to mammals is suggested by the structural features of apAPH.