According to evolutionary models of gene duplication, paralogous genes are functionally identical after duplication and slowly diverge by partitioning ancestral functions and/or acquiring new ones until becoming functionally independent. Paralogs may influence each other’s evolutionary fate during this period. First, the functional redundancy of the two duplicates may affect the fitness consequences of mutations in one member of a pair, for instance by masking deleterious mutations through functional compensation. Second, the function of the two duplicates may be functionally linked by mechanisms such as cross-regulation or physical interaction between gene products. The two paralogs could thus evolve as a single functional unit. Here we study this interdependency in the yeast protein interaction network by examining whether duplicated genes affect each other’s protein-protein interactions when deleted. We tested 56 pairs of duplicated genes in the yeast Saccharomyces cerevisiae and found that for a large fraction of them, deleting one duplicate leads to gains of interaction by the other, following patterns that are consistent with a mechanism of functional compensation. We also found an unexpectedly large proportion of pairs that exhibit functional dependency, i.e. partial or complete loss of protein-protein interactions of the remaining paralog after the deletion of its sister copy. Our results provide a molecular mechanism for functional compensation between paralogs, show that functional dependency is widespread among duplicate pairs and suggest that paralogs often do not diverge independently but constrain each other’s evolutionary fate.