Cells adapt to different conditions via gene expression that tunes metabolism for maximal fitness. Constraints on cellular proteome may limit such expression strategies and introduce trade-offs. Resource allocation under proteome constraints has explained regulatory strategies in bacteria. It is unclear, however, to what extent these constraints can predict evolutionary changes, especially for microorganisms that evolved under nutrient-rich conditions, i.e., multiple available nitrogen sources, such as Lactococcus lactis. Here, we present a proteome-constrained genome-scale metabolic model of L. lactis (pcLactis) to interpret growth on multiple nutrients. Through integration of proteomics and flux data, in glucose-limited chemostats, the model predicted glucose and arginine uptake as dominant constraints at low growth rates. Indeed, glucose and arginine catabolism were found upregulated in evolved mutants. At high growth rates, pcLactis correctly predicted the observed shutdown of arginine catabolism because limited proteome availability favored lactate for ATP production. Thus, our model-based analysis is able to identify and explain the proteome constraints that limit growth rate in nutrient-rich environments and thus form targets of fitness improvement.