The concept of molecular co-evolution drew attention in recent years as the basis for several algorithms for the prediction of protein–protein interactions. While being successful on specific data, the concept has never been tested on a large set of proteins. In this chapter we analyze the feasibility of the co-evolution principle for protein–protein interaction prediction through one of its derivatives, the correlated divergence model. Given two proteins, the model compares the patterns of divergence of their families and assigns a score based on the correlation between the two. The working hypothesis of the model postulates that the stronger the correlation the more likely is that the two proteins interact. Several novel variants of this model are considered, including algorithms that attempt to identify the subset of the database proteins (the homologs of the query proteins) that are more likely to interact. We test the models over a large set of protein interactions extracted from several sources, including BIND, DIP, and HPRD.