The maintenance of duplicated genes is thought to protect cells from genetic perturbations, but the molecular basis of this robustness is largely unknown. By measuring the interaction of yeast proteins with their partners in wild-type cells and in cells lacking a paralog, we found that 22 out of 56 paralog pairs compensate for the lost interactions. An equivalent number of pairs exhibit the opposite behavior and require each other's presence for maintaining their interactions. These dependent paralogs generally interact physically, regulate each other's abundance, and derive from ancestral self-interacting proteins. This reveals that gene duplication may actually increase mutational fragility instead of robustness in a large number of cases.