Tissue transglutaminase (TG2) is a multifunctional enyzme involved in cell growth and differentiantion, receptor mediated endocytosis, cell adhesion and morphology, stabilization of extracellular matrix, membrane trafficking and structure/function, signal transduction, regulation of cytoskeleton and apoptosis. Multiple lines of evidence suggest an involvement of TG2 autoimmune diseases, cancer and in neurodegenerative diseases, including Alzheimer's disease, progressive supranuclear palsy, Huntington's disease and Parkinson's disease. In all of the neurodegenerative diseases examined to date, TG2 activity is upregulated in selectively vulnerable brain regions, TG2 proteins are associated with inclusion bodies characteristic of the diseases, and prominent proteins in the inclusion bodies are modified by TG2 enzyme. It is important to identify TG2 substrates as they may offer an understanding of how the TG2-catalyzed post-translational modification has an impact on physiology and disease. Identification of these substrates may lead to novel drug targets and new diagnostic markers for several TG2-related diseases. A variety of different methods have been proposed for the identification of TG2 substrates. In this work we applied a new method for identification of TG2 substrates (interactors) by using a selection of cDNA phage display libraries followed by massive gene sequencing with 454 system. Ranking and analysis of more than 120,000 sequences allowed us to identify several potential substrates and interactors, which were subsequently confirmed in functional assays. Within the identified clones, some had been previously described as interacting proteins (fibronectin, SMOC1, EIF4G2, MYO18A, GSTO2), while others were new. When compared to standard systems, such as microtiter ELISA, the method described here is dramatically faster and yields far more information about the interaction under study, allowing better characterization of complex systems. For example, in the case of fibronectin, it was possible to identify the specific domains involved in the interaction. We expect that this approach to library and selection analysis can also be extended to other methods traditionally used to study protein-protein interactions, as well as to the study of the selection of peptides and antibodies by phage display.