The emergence of the coiled coils of interacting partners are correlated. Co-evolution of coiled coils indicates conservation of protein-protein interactions. Prediction capability of the approach relates to quality of experimental evidence. Paralog biases alone cannot explain the results. Our method will improve when a larger number of distributed proteomes are available.