Aminopeptidase P (APPro) is a manganese-dependent enzyme that cleaves the N-terminal amino acid from polypeptides where the second residue is proline. APPro shares a similar fold, substrate specificity, and catalytic mechanism with methionine aminopeptidase and prolidase. To investigate the roles of conserved residues at the active site, seven mutant forms of APPro were characterized kinetically and structurally. Mutation of individual metal ligands selectively abolished binding of either or both Mn(II) atoms at the active site, and none of these metal-ligand mutants had detectable catalytic activity. Mutation of the conserved active site residues His243 and His361 revealed that both are required for catalysis. We propose that His243 stabilizes substrate binding through an interaction with the carbonyl oxygen of the requisite proline residue of a substrate and that His361 stabilizes substrate binding and the gem-diol catalytic intermediate. Sequence, structural, and kinetic analyses reveal that His350, conserved in APPro and prolidase but not in methionine aminopeptidase, forms part of a hydrophobic binding pocket that gives APPro its proline specificity. Further, peptides in which the required proline residue is replaced by N-methylalanine or alanine are cleaved by APPro, but they are extremely poor substrates due to a loss of interactions between the prolidyl ring of the substrate and the hydrophobic proline-binding pocket.