Determining protein interaction networks and predicting network changes in time and space are crucial to understanding and modeling a biological system. In the past few years, the combination of experimental and computational tools has allowed great progress toward reaching this goal. Experimental methods include the large-scale determination of protein interactions using two-hybrid or pull-down analysis as well as proteomics. The latter one is especially valuable when changes in protein concentrations over time are recorded. Computational tools include methods to predict and validate protein interactions on the basis of structural information and bioinformatics tools that analyze and integrate data for the same purpose. In this review, we focus on the use of structural information in combination with computational tools to predict new protein interactions, to determine which interactions are compatible with each other, to obtain some functional insight into single and multiple mutations, and to estimate equilibrium and kinetic parameters. Finally, we discuss the importance of establishing criteria to biologically validate protein interactions.