Genetic redundancy means that two genes can perform the same function. Using a comprehensive phylogenetic analysis, we show here in both Saccharomyces cerevisiae and Caenorhabditis elegans that genetic redundancy is not just a transient consequence of gene duplication, but is often an evolutionary stable state. In multiple examples, genes have retained redundant functions since the divergence of the animal, plant and fungi kingdoms over a billion years ago. The stable conservation of genetic redundancy contrasts with the more rapid evolution of genetic interactions between unrelated genes and can be explained by theoretical models including a 'piggyback' mechanism in which overlapping redundant functions are co-selected with nonredundant ones.