Microbial growth relies on the presence of several nutrients, including elemental nutrients such as carbon and nitrogen, as well as complex nutrients like vitamins and amino acids. Evidence from biogeochemistry, especially in aquatic environments, suggests that multiple nutrients may be simultaneously rare in nature and therefore limit growth. However, we poorly understand how this co-limitation affects microbial growth, physiology, and evolution. This is especially important in the context of multi-species communities, where pervasive cross-feeding of many nutrients leads to the coevolution of nutrient limitation between species. We introduce a theoretical framework for understanding and quantifying nutrient limitation, which we apply to an evolutionary model to show how limitation for multiple nutrients evolves. We find that evolution can spontaneously drive nutrient uptake to match environmental availability, leading to co-limitation of multiple nutrients. We show how this result depends on the interaction between nutrients and supply of adaptive mutations. In particular, we demonstrate how nutrient limitation coevolves across species in cross-feeding communities. This prediction is consistent with observed correspondences between the elemental composition of microbes and their environments. It suggests that co-limitation may be a generic property of microbial communities due to evolutionary forces.