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.