MOTIVATION: Interacting pairs of proteins should co-evolve to maintain functional and structural complementarity. Consequently, such a pair of protein families shows similarity between their phylogenetic trees. Although the tendency of co-evolution has been known for various ligand-receptor pairs, it has not been studied systematically in the widest possible scope. We investigated the degree of co-evolution for more than 900 family pairs in a global protein structural interactome map (PSIMAP--a map of all the structural domain-domain interactions in the PDB). RESULTS: There was significant correlation in 45% of the total SCOPs Family level pairs, rising to 78% in 454 reliable family interactions. Expectedly, the intra-molecular interactions between protein families showed stronger co-evolution than inter-molecular interactions. However, both types of interaction have a fundamentally similar pattern of co-evolution except for cases where different interfaces are involved. These results validate the use of co-evolution analysis with predictive methods such as PSIMAP to improve the accuracy of prediction based on "homologous interaction". The tendency of co-evolution enabled a nearly 5-fold enrichment in the identification of true interactions among the potential interlogues in PSIMAP. The estimated sensitivity was 79.2%, and the specificity was 78.6%. AVAILABILITY: The results of co-evolution analysis are available online at http://www.biointeraction.org