Resource limitation and predation mortality are major determinants of microbial population dynamics, and optimization for either aspect is considered to imply a trade-off with respect to the other. Adaptation to these selective factors may, moreover, lead to disadvantages at rich growth conditions. We present an example of a concomitant evolutionary optimization to both, substrate limitation and predation in an aggregate-forming freshwater bacterial isolate, and we elucidate an underlying genomic mechanism. Bacteria were propagated in serial batch culture in a nutrient-restricted environment either with or without a bacterivorous flagellate. Strains isolated after 26 growth cycles of the predator–prey co-cultures formed as much total biomass as the ancestor at ancestral growth conditions, albeit largely reallocated to cell aggregates. A ~273 kbp genome fragment was lost in three strains that had independently evolved with predators. These strains had significantly higher growth yield on substrate-restricted media than others that were isolated from the same treatment before the excision event. Under predation pressure, the isolates with the deletion outcompeted both, the ancestor and the strains evolved without predators even at rich growth conditions. At the same time, genome reduction led to a growth disadvantage in the presence of benzoate due to the loss of the respective degradation pathway, suggesting that niche constriction might be the price for the bidirectional optimization.