A goal of contemporary proteome research is the elucidation of protein-protein interactions in a cell. Based on currently available protein-protein interaction and domain data of S. cerevisiae, we introduce a novel method, Maximum Specificity Set Cover (MSSC), to predict protein-protein interactions. MSSC features three stages: First, MSSC selects high quality protein-protein interactions based on a clustering measure. Second, MSSC assigns probabilities to domain pairs. Third, MSSC uses the domain pairs to infer protein-protein interactions. We also modified MSSC to include the possibility of having more than one domain from each protein causing the protein-protein interaction. MSSC allows us to predict previously unknown protein-protein interactions with a degree of sensitivity and specificity that clearly out-scores other approaches. MSSC achieved 86% sensitivity and 62% specificity using 80% of the high quality interactions in the DIP database. The predicted interaction network preserves the characteristics of the initial web of known protein interactions. We also observe high levels of co-expression among putative interactions. We also observe high levels of co-expression among putative interactions. We extend our method to infer protein-protein interactions in multicellular organisms where protein-protein interaction data currently does not exist. Starting from predictions in yeast, we find a set of orthologous interactions in A. thaliana, C. elegans, D. melanogaster, M. musculus, and H. sapiens.