Transglutaminases are best known for their ability to catalyze protein cross-linking reactions that impart chemical and physical resilience to cellular structures. Here, we report the crystal structure and characterization of Tgl, a transglutaminase from the bacterium Bacillus subtilis. Tgl is produced during sporulation and cross-links the surface of the highly resilient spore. Tgl-like proteins are found only in spore-forming bacteria of the Bacillus and Clostridia classes, indicating an ancient origin. Tgl is a single-domain protein, produced in active form, and the smallest transglutaminase characterized to date. We show that Tgl is structurally similar to bacterial cell wall endopeptidases and has an NlpC/P60 catalytic core, thought to represent the ancestral unit of the cysteine protease fold. We show that Tgl functions through a unique partially redundant catalytic dyad formed by Cys116 and Glu187 or Glu115. Strikingly, the catalytic Cys is insulated within a hydrophobic tunnel that traverses the molecule from side to side. The lack of similarity of Tgl to other transglutaminases together with its small size suggests that an NlpC/P60 catalytic core and insulation of the active site during catalysis may be essential requirements for protein cross-linking.