Yeast peptide:N-glycanase (Png1p; PNGase), a deglycosylation enzyme involved in the proteasome dependent degradation of proteins, has been reported to be a member of the transglutaminase superfamily based on sequence alignment. In this study we have investigated the structure-function relationship of Png1p by site-directed mutagenesis. Cys-191, His-218, and Asp-235 of Png1p are conserved in the sequence of factor XIIIa, where these amino acids constitute a catalytic triad. Point mutations of these residues in Png1p resulted in complete loss in activity, consistent with a role for each in catalyzing deglycosylation of glycoproteins. Other conserved amino acid residues, Trp-220, Trp-231, Arg-210, and Glu-222, were also vitally important for folding and structure stability of the enzyme as revealed by circular dichroism analysis. The potential effects of the mutations were predicted by mapping the conserved amino acids of Png1p within the known three-dimensional structure of factor XIIIa. Our data suggest that the lack in enzyme activity when any of the catalytic triad residues is mutated is either due to the absence of charge relay in the case of the triad or due to the disruption of the native fold of the enzyme. These findings strongly suggest a common evolutionary lineage for the PNGases and transglutaminases.