This goal of this dissertation is to predict, using computational techniques, the motifs that mediate interactions between proteins. The strategy for inferring interacting motifs is based on evolutionary correlation, which states that the patterns of mutations in two proteins that interact are correlated across a set of species. This dissertation makes three important contributions: (1) Defines and implements a new paradigm for functionally equivalent proteins, called MoLFunCs (most likely functional counterparts), (2) Exhaustively samples motifs in the two proteins to identify putative interaction sites and (3) Estimates the significance of correlations in genomic context. The identification of MoLFunCs is necessary to define the sample set of species across which correlated mutations are identified. Evolutionary correlation is inferred using the Mirror-Tree technique, which computes correlations between distance matrices that correspond to the phylogenetic trees of the two sets of proteins. This thesis borrows ideas and methods of analysis from other domains of research such as Information Retrieval. The effectiveness of the method is demonstrated using a membrane protein complex (subunits - Kv1.2 and Beta2) whose 3D structure has been recently identified. Kv1.2 is a voltage-gated potassium channel whose function can be modulated by the Beta2 subunit. Our technique allows us to successfully predict the interacting motifs as highly correlated sites between the two proteins.