Adaptive evolution is generally assumed to progress through the accumulation of beneficial mutations. However, as deleterious mutations are common in natural populations, they generate a strong selection pressure to mitigate their detrimental effects through compensatory genetic changes. This process can potentially influence directions of adaptive evolution by enabling evolutionary routes that are otherwise inaccessible. Therefore, the extent to which compensatory mutations shape genomic evolution is of central importance. Here, we studied the capacity of the baker's yeast genome to compensate the complete loss of genes during evolution, and explored the long-term consequences of this process. We initiated laboratory evolutionary experiments with over 180 haploid baker's yeast genotypes, all of which initially displayed slow growth owing to the deletion of a single gene. Compensatory evolution following gene loss was rapid and pervasive: 68% of the genotypes reached near wild-type fitness through accumulation of adaptive mutations elsewhere in the genome. As compensatory mutations have associated fitness costs, genotypes with especially low fitnesses were more likely to be subjects of compensatory evolution. Genomic analysis revealed that as compensatory mutations were generally specific to the functional defect incurred, convergent evolution at the molecular level was extremely rare. Moreover, the majority of the gene expression changes due to gene deletion remained unrestored. Accordingly, compensatory evolution promoted genomic divergence of parallel evolving populations. However, these different evolutionary outcomes are not phenotypically equivalent, as they generated diverse growth phenotypes across environments. Taken together, these results indicate that gene loss initiates adaptive genomic changes that rapidly restores fitness, but this process has substantial pleiotropic effects on cellular physiology and evolvability upon environmental change. Our work also implies that gene content variation across species could be partly due to the action of compensatory evolution rather than the passive loss of genes. While core cellular processes are generally conserved during evolution, the constituent genes differ somewhat between related species with similar lifestyles. Why should this be so? In this work, we propose that gene loss may initially be deleterious, but organisms can recover fitness by the accumulation of compensatory mutations elsewhere in the genome. To investigate this process in the laboratory, we investigated 180 haploid yeast strains, each of which initially displayed slow growth owing to the deletion of a single gene. Laboratory evolutionary experiments revealed that defects in a broad range of molecular processes can readily be compensated during evolution. Genomic analyses and functional assays demonstrated that compensatory evolution generates hidden genetic and physiological variation across parallel evolving lines, which can be revealed when the environment changes. Strikingly, despite nearly full recovery of fitness, the wild-type genomic expression pattern is generally not restored. Based on these results, we argue that genomes undergo major changes not simply to adapt to external conditions but also to compensate for previously accumulated deleterious mutations.