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).