Formation of a stable fibrin clot is dependent on interactions between factor XIII and fibrin. We have previously identified a key residue on the αC of fibrin(ogen) (Glu396) involved in binding activated factor XIII-A2 (FXIII-A2*); however, the functional role of this interaction and binding site(s) on FXIII-A2* remains unknown. Here we (1) characterized the functional implications of this interaction; (2) identified by liquid-chromatography–tandem mass spectrometry the interacting residues on FXIII-A2* following chemical cross-linking of fibrin(ogen) αC389-402 peptides to FXIII-A2*; and (3) carried out molecular modeling of the FXIII-A2*/peptide complex to identify contact site (s) involved. Results demonstrated that inhibition of the FXIII-A2*/αC interaction using αC389-402 peptide (Pep1) significantly decreased incorporation of biotinamido-pentylamine and α2-antiplasmin to fibrin, and fibrin cross-linking, in contrast to Pep1-E396A and scrambled peptide controls. Pep1 did not inhibit transglutaminase-2 activity, and incorporation of biotinyl-TVQQEL to fibrin was only weakly inhibited. Molecular modeling predicted that Pep1 binds the activation peptide cleft (AP-cleft) within the β-sandwich domain of FXIII-A2* localizing αC cross-linking Q366 to the FXIII-A2* active site. Our findings demonstrate that binding of fibrin αC389-402 to the AP-cleft is fundamental to clot stabilization and presents this region of FXIII-A2* as a potential site involved in glutamine-donor substrate recognition.