Adaptation of one set of traits is often accompanied by attenuation of traits important in other selective environments, leading to fitness trade-offs. The mechanisms that either promote or prevent the emergence of trade-offs remain largely unknown, and are difficult to discern in most systems. Here, we investigate the basis of trade-offs that emerged during experimental evolution of Methylobacterium extorquens AM1 to distinct growth substrates. After 1500 generations of adaptation to a multi-carbon substrate, succinate (S), many lineages had lost the ability to use one-carbon compounds such as methanol (M), generating a mixture of M(+) and M(-) evolved phenotypes. We show that trade-offs in M(-) strains consistently arise via antagonistic pleiotropy through recurrent selection for loss-of-function mutations to ftfL (formate-tetrahydrofolate ligase), which improved growth on S while simultaneously eliminating growth on M. But if loss of FtfL was beneficial, why were M trade-offs not found in all populations? We discovered that eliminating FtfL was not universally beneficial on S, as it was neutral or even deleterious in certain evolved lineages that remained M(+) . This suggests that sign epistasis with earlier arising mutations prevented the emergence of mutations that drove trade-offs through antagonistic pleiotropy, limiting the evolution of metabolic specialists in some populations.