The structure and connectivity of protein-protein interaction (PPI) networks are maintained throughout evolution by coordinated changes (coevolution) of network proteins. Despite extensive research, relatively little is known regarding the molecular basis and functional implications of the coevolution of PPI networks. Here, we used proliferating cell nuclear antigen, a hub protein that mediates DNA replication and repair in eukaryotes, as a model system to study the coevolution of PPI networks in fungi. Using a combined bioinformatics and experimental approach, we discovered that PCNA-partner interactions tightly coevolved in fungal species, leading to specific modes of recognition. We found that fungal proliferating cell nuclear antigen-partner interaction networks diverged into two distinct groups as a result of such coevolution and that hybrid networks of these groups are functionally noncompatible in Saccharomyces cerevisiae. Our results indicate that the coevolution of PPI networks can form functional barriers between fungal species, and thus can promote and fix speciation.