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, Q-x-P--D-(P), Q-x-P-, and Q-x-x--D-P; Factor XIIIa, Q-x-x--x-W-P (where x and represent a non-conserved and a hydrophobic amino acid, respectively). We further confirmed that the sequences were favored for transamidation using a 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.