Mammalian transglutaminase (TGase) catalyzes covalent cross-linking of peptide-bound lysine residues or incorporation of primary amines to limited glutamine residues in substrate proteins. Using an unbiased M13 phage display random peptide library, we developed a screening system to elucidate primary structures surrounding reactive glutamine residue(s) that are preferred by TGase. Screening was performed by selecting phage clones expressing peptides that incorporated biotin-labeled primary amine by the catalytic reactions of TGase 2 and activated Factor XIII (Factor XIIIa). We identified several amino acid sequences that were preferred as glutamine donor substrates, most of which have a marked tendency for individual TGases: TGase 2, QxPphiD(P), QxPphi, and QxxphiDP; Factor XIIIa, QxxphixWP (where x and phi represent a non-conserved and a hydrophobic amino acid, respectively). We further confirmed that the sequences were favored for transamidation using modified glutathione S-transferase (GST) for recombinant peptide-GST fusion proteins. Most of the fusion proteins exhibited a considerable increase in incorporation of primary amines over that of modified GST alone. Furthermore, we identified the amino acid sequences that demonstrated higher specificity and inhibitory activity in the cross-linking reactions by TGase 2 and Factor XIIIa.