Many bacterial lineages lack seemingly essential metabolic genes. Previous work suggested selective benefits could drive the loss of biosynthetic functions from bacterial genomes when the corresponding metabolites are sufficiently available in the environment. However, the factors that govern this ‘genome streamlining’ remain poorly understood. Here we determine the effect of plasticity and epistasis on the fitness of Escherichia coli genotypes from whose genome biosynthetic genes for one, two, or three different amino acids have been deleted. Competitive fitness experiments between auxotrophic mutants and prototrophic wild type cells in one of two carbon environments revealed that plasticity and epistasis strongly affected the mutants’ fitness individually and interactively. Positive and negative epistatic interactions were prevalent, yet on average cancelled each other out. Moreover, epistasis correlated negatively with the expected effects of combined auxotrophy-causing mutations, thus producing a pattern of diminishing returns. Moreover, computationally analysing 1,432 eubacterial metabolic networks revealed that most pairs of auxotrophies co-occurred significantly more often than expected by chance, suggesting epistatic interactions and/ or environmental factors favoured these combinations. Our results demonstrate that both the genetic background and environmental conditions determine the adaptive value of a loss-of-biochemical-function mutation and that fitness gains decelerate, as more biochemical functions are lost.