Current motif discovery methods can only detect individual motifs in groups of protein sequences-they do not discover potentially-interacting motif pairs underlying the interactions between the proteins. Such interacting motif pairs can be useful for the design and discovery of new drugs. Recent technological advances have made available large datasets of experimentally-detected protein-protein interactions. The functionally-induced co-occurring patterns inherent in the pairwise protein interaction data can be exploited to discover novel interacting motif pairs. In this work, we present an automated method to discover novel interacting motif pairs from large datasets of protein-protein interactions. Using our method, we discovered 9,045 novel interacting motif pairs from a large dataset of 78,390 interacting yeast proteins. Our method was able to discover motif pairs that are highly deterministic of protein interaction, with many of the motifs corresponding to structural contact sites in protein complexes, or experimentally-determined binding sites reported in the literature.